资源描述：
《2004数据结构考试试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、承诺：我将严格遵守考场纪律，并知道考试违纪、作弊的严重性，承担由此引起的一切后果。专业班级学号学生签名：承诺：我将严格遵守考场纪律，并知道考试违纪、作弊的严重性，承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2004—2005学年第1学期考试卷数据结构课程课程类别：必修闭卷题号一二三四五六七八九总分分数评卷人一，填空题（每空1分，共20分）1，现有一个程序，它能够处理气象卫星收集的数据用来预测今后两天的天气，但是却要算上将近一个星期，故其在实践中应该来讲是没有什么意义的，不能称其为算法，因为它违背了算法的___可行性_______。2，若设L是
2、带表头结点的单链表的表头指针，则语句L->next=L->next->next的作用是__删除单链表的第一个结点_____。（其中next是节点指针域）3，我国的权力机构由各级人民代表大会组成，如果将所有代表大会当作一个数据整体，则根据我国的实际管理关系，用数据结构里面的术语，它们之间是__树状____关系。4，在线性表的顺序存储实现中，假设线性表的长度为n，则平均插入一个数据元素平均要移动元素的次数为___n/2____________。（假设元素插入到各个位置的概率相同）5，后缀表达式“45*32+-4-”的值为___11____。（注意所有数都为1位
3、个位数）6，设有一个顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素的出栈顺序为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为___3_____。7，设有关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用步长为5,3,1的Shell排序法，则进行到步长为3之后，执行步长为1之前的结果是_A,D,C,M,H,F,Q,Q,X,R,S,Y____；若采用以最后一个元素为分界元素的快速排序法，则一趟扫描的结果是__Q,H,C,F,Q,A,M,S,R,D,X,Y_____。8，一个
4、具有567个结点的完全二叉树，其叶子结点个数为__284__。9，一颗二叉树有13个结点，则这颗二叉树的高度最大为___14___,最小为___4_______。10，在AOV网中，顶点表示___活动__，边表示__活动间优先关系____。第10页共10页1，哈希表的装填因子含义___哈希表的装满程度___。2，有一个整数有序序列（4，6，8，34，45，67，89，123），若采用二分查找，则查找89要进行__3_____次比较。3，一颗二叉树的叶结点分别为（4，6，7，2，5，67），则这颗树有__5___个度为2的结点。4，用邻接矩阵存储图，占用存储
5、空间数与图中顶点个数__有_关，与边数_无_关。二，选择题（每题2分，共20分）1，一种抽象数据类型包括数据和（B）两个部分。A.数据类型B.数据操作C.数据抽象D.类型说明2，设循环队列中数组的下标范围是0..n-1，其头尾的下标分别为f和r，则其元素个数为（A）。A、(r-f+n)%nB、(r-f)%n+1C、r-f+1D、r-f3,由权值分别为3，8，6，2，2的叶子结点生成一棵哈夫曼树，它的带权路径长度为（C）A14B44C45D214,以下序列中不符合堆定义的是__D__。A．(102，87，100，79，82，62，84，42，22，12，68
6、)B．(102，100，87，84，82，79，68，62，42，22，12)C．(12，22，42，62，68，79，82，84，87，100，102)D．(102，87，42，79，82，62，68，100，84，12，22)5,解决散列法中出现的冲突问题常采用的方法是（D）。A.数字分析法、除留余数法、平方取中法B.数字分析法、除留余数法、线性探测法C.数字分析法、线性探测法、双散列法D.线性探测法、二次探测法、开放地址拉链法6,设双向循环链表中结点的结构为（data,lLink,rLink），且不带表头结点。若想在指针p所指结点之后插入指针s所指结
7、点，则应执行下列哪一个操作？（D）A.p->rLink=s;s->lLink=p;p->rLink->lLink=s;s->rLink=p->rLink;B.p->rLink=s;p->rLink->lLink=s;s->lLink=p;s->rLink=p->rLink;C.s->lLink=p;s->rLink=p->rLink;p->rLink=s;p->rLink->lLink=s;第10页共10页D.s->lLink=p;s->rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;//7,设有一个n´n的对称矩阵
8、A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于
