浙江工业大学数据结构试卷

1、精选优质文档-倾情为你奉上浙工大0708学年 数据结构试卷A一、单选题. (201 = 20分)1常用的算法时间复杂度中，按照复杂度优劣排列正确的是（ ）。A) O(1)O(log2n) O(n) O(n2) O(nlog2n) B) O(1)O(n) O(log2n)O(n2) O(nlog2n)C) O(1)O(log2n) O(n) O(nlog2n ) O(n2)D) O(1)O(n) O(l og2n)O(nlog2n)O(n2)2线性表如果采用链式存储结构时，要求内存中可用存储单元的地址（ ）。A) 必须是连续的 B) 部分地址必须是连续的 C) 一定是不连续的 D) 连续或不连续

2、都可以3用于解决图的点对之间的最短路径的算法是（ ）。A) 图的深度优先遍历算法 B) 图的Dijkstra算法C) 图的Warshall算法 D) 图的floyd算法4以下的数据结构中，是线性结构的是（ ）。A) 栈 B) 散列 C) 图 D) 优先队列5以下满足队列特点是（ ）。A) 后到先服务B) 在相同的端点添加和删除元素 C) 在一端添加元素，在另一端删除元素D) 先进后出6. 设某数据结构的二元组形式表示为A=(D，R)，D=01，02，03，04，05，06，07，08，09，R=r，r=，则数据结构A是（ ）。 A)线性结构B)树型结构C)链式结构 D)图型结构7根据二叉树的定

3、义， 3个结点的二叉树有几种形态（ ）。A) 6 B) 5 C) 4 D) 38下列应用中，需使用队列的是（ ）。A）实现递归算法 B）实现树的层次遍历C）实现表达式计算 D）实现深度优先搜索9使用按照中序遍历二叉排序树，得到的遍历序列满足（ ）。A)乱序 B) 降序 C) 升序 D) 情况随机10设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（ ）。A)15，25，35，50，20，40，80，85，36，70B)15，25，35，50，80，20，85，40

4、，70，36C)15，25，35，50，80，85，20，36，40，70D)15，25，35，50，80，20，36，40，70，8511在以下的序列中，哪个是最小堆？（ ） A)29，53，56，72，34，67，86 B) 86，72， 34，48， 56， 53，29 C)29，33，50，72，48，92，133 D) 34，42，53， 12， 5， 29， 3312散列表长 m = 15, 散列函数hash(key) = key % 13, 表中已经有了4个结点, 关键字分别是18, 32, 59, 73, 其余地址为空，如是采用开地址散列(线性探测法)处理冲突，那么关键字109

5、的结点地址为（ ）。A) 8 B) 9 C) 5 D) 413采用牺牲元素法来构造循环队列时，长度为n的向量可以存放的元素个数为:（ ）。 A) n-2 B) n-1 C) n D) n+1 14如果对二叉树采用的遍历方式是右子树左子树根，那么左下图的二叉树相应的遍历序列为（ ）。A) 9, 7, 5, 4, 1 B) 4, 1, 9, 7, 5 C) 7, 9, 5, 4, 1 D) 9, 7, 4, 1, 55 71 9415将一棵有99个结点的完全二叉树按顺序编号，根结点的编号为0,那么编号为49的结点的右子结点的编号为（ ）。 A) 98 B) 99 C) 100 D) 不存在16一个

6、栈的入栈序列是a,b,c,d,下列出栈序列中不可能的出栈序是哪个？（ ）。A) abcd B) acbd C) dcba D) cabd1710000个结点要构造二叉树(树高从0层开始)，则最高的二叉树和最低的二叉树的树高为（ ）。A）5000, 100 B）10000, 18C）5000,14 D）99999, 1418如下图，从顶点1出发，按照广度优先规则遍历，可能得到的序列为（ ）。7216453A) B) C) D) 19设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。v1v2v3v4v7v5v6A）5 B）6 C）7 D）820已知有向图G = (V, E), 如右

7、图所示，G的可能的拓扑排序为（ ）。A) V1, V3, V4, V6, V2, V5, V7 B) V1, V3, V5, V6, V4, V2, V7C) V1, V3, V4, V5, V2, V6, V7 D) V1, V2, V5, V3, V4, V6, V7二、填空题(102 = 20分)1对于声明：ListStack myStack; 有一些操作：myStack.push(A); myStack.push(K);myStack.push(D); myStack.pop();myStack.push(H); myStack.push(K); myStack.pop(); mySt

8、ack.pop();myStack.push(D); 此时，栈内元素从栈底向栈顶依次为_（1）_。 2 一个二叉树的前序遍历结果为：ABDEHCFIGJ; 中序遍历结果为：DBEHAIFCJG;请给出这个二叉树的后序便历序列_（2）_。 3表达式 f+(a+b)/(d-e)*2 对应的后缀表达式是_（3）_。4求如下程序段的时间复杂度，复杂度采用大O表示。_ （4） _。/假设n, data 均有定义int low=0;int high=n;while(lowhigh)int mid=(low+high)/2;if(datamid=value) cout”find the data at:”m

9、id;else if(datamidvalue) low=mid+1;else high=mid;cout”cant find the data,the last searching:”low;5使用上题的策略对排序向量：170，275，426，503，509，512，612，653，677，703，765，897，908检索元素703，请问依次比较的元素为_（5）_。6假设有向量(Q, H, C, Y, P, A, M, S, R, D, F, X) ，如果要将该向量调整成最大堆，则结果是_（6）_； 如果要将该向量按字母升序排列，则采用选择排序的第二趟排序的结果是_（7）_；采用快速排序的

10、第二趟排序的结果是_（8）_。 7有排序二叉树的原始图如下所示:（二叉树的原始图）在原始图上添加结点77后，该排序树变为_（9）_在原始图上删除结点112，该排序树变为_（10）_三、算法分析与设计:（60分）1将关键码序列为C, B, X, W, U, V, Y依次插入到一个空的AVL树中，画出每次插入完成后的AVL树 （8分）2已知带权图如图所示，请给出它的邻接矩阵表示形式。（5分）3 设待排序的关键码序列为最大堆30，28，20，18，12，10，16，6，2，试写出使用堆排序的前3趟结果。（6分） 4. 有9个关键码的开地址散列向量 32，13，49，55，22，39，20，97，56

11、，散列函数为取余运算（即%11，如关键码32的向量地址为32%11 = 10），散列表空间为11个单元。试分别完成按以上关键码顺序插入到线性开地址散列解决冲突的散列表之后的结果。（5分）5设有无向图G，要求给出用普里姆算法构造最小生成树的全过程。（6分）6. 对于下图，试模拟Dijkstra算法，给出从编号为A的顶点出发到其它各个结点的最短路径的过程。（10分）121025281618221424816AGBFEDC7假设用于通讯的电文仅有6个字母abcdef组成，字母在电文中出现的频率分别为7，19，5，16，42，11。试为这6个字母设计哈夫曼编码。（8分）8. 已知一个队列的模板类如下#

12、define queue_size 1000template class queueVector protected: T dataqueue_size;/ 队列空间int nextSlot; /入队指示int nextUse;/出队指示 public: / 构造和析构函数queueVector ( );queueVector (const queueVector& other); T dequeue( );/出队动作 void enqueue(T value);/入队动作;请完善这个这个队列。已知模板类的各个函数实现情况如下，请补充完整。template queueVector:queueV

13、ector ( ) /初始化队列：设置队列相关属性初始值。 nextSlot=0; nextUse=0;template queueVector:queueVector (const queueVector& other )/拷贝构造函数，根据参数初始化队列对象本身。（4分） template T queueVector:dequeue ( ) /出队动作：若队列不空，则删除队列首元素，并返回该元素。（4分） template void queueVector:enqueue (T value )/入队动作：若队列不满，则往队列末尾添加元素。（4分）一、选择题（20分）1.C 2.D 3.D

14、4.A 5.C6. B,D 7.B 8.B 9.C 10.A11.C 12.B 13.B 14.D 15.D16.D 17.D(送分) 18.C 19.A 20.A二、填空题. （20分）1（1）A K D 注意：从栈底到栈顶，若写成D K A，得1分。2（2）D H E B I F J G C A3（3）f a b + d e - / 2 * +4（4）O(log2n)5（5）6612,10765,8677,9703 或 6612,97036（6）Y S X R P C M H Q D F A （7）A C H Y P Q M S R D F X （8）A D C F P H M Q R S

15、 Y X575044130796093134575044112796093771341307（9） （10）三、算法分析设计(60分)1（8分）WUCVCBUWCBX右单旋WCBXCBXCB右左双旋WXBXUYV1分 1 分 1分 1分 2分 2分2（5分）ABCDEMA08010B20050C030100D90040E0M1502边1分，共9边；对角线为0，1分；3（6分）2281820106121630调整281862010212163030281820101612162 2分20186161028122302186201028121630调整 2分18126161028220302186

16、161028122030调整 2分4（5分）32%11=10 13%11=2 49%11=5 55%11=0 22%11=0 39%11=6 20%11=9 97%11=9 56%11=155 22 13 97 56 49 39 20 320 1 2 3 4 5 6 7 8 9 102个数据1分，扣完为止。5（6分）任选1点出发即可，1点得1分，共6点，最小生成树的权值是11。465231652315231231311 1分 1分 1分 1分 1分 1分6（10分）从A点出发；一组数据1.5分，共6组数据，完全正确再得1分。0 8 10 28A B C D E F GA A，D A-D 80

17、26 8 32 10 28A B C D E F GA A，D，F A-F 10 0 26 8 32 10 28 A B C D E F GA A，D，F，B A-D-B 26 0 26 38 8 32 10 28A B C D E F GA A，D，F，B，G A-G 280 26 38 8 32 10 28A B C D E F GA A，D，F，B，G，E A-D-E 320 26 38 8 32 10 28A B C D E F GA A，D，F，B，G，E，C A-D-B-C 387（8分）答案不唯一，但是WPL=228；图1分，每个编码1分（6分），完全正确得1分。或 写出构造哈夫

18、曼树的全过程（6分），编码（2分）。10042(e)58352319(b)16(d)11(f)125(c)7(a) 为哈夫曼树设计编码，左子树为0，右子树为1；a:0000 b:011 c:0001 d:010 e:1 f:0018.（12分） template queueVector:queueVector (const queueVector& other )/拷贝构造函数，根据参数初始化队列对象本身。If(other.nextUse= =other.nextSlot) nextSlot=0; nextUse=0; （1分或0分）else nextSlot=other.nextSlot; 1分 nextUse=other.nextUse; 1分 for(int i=0;i queue_size;i+) datai=other.datai; 2分（或1分）template T queueVector:dequeue ( ) /出队动作：若队列不空，则删除队列首元素，并返回该元素。assert (!isEmpty() ; /首先要判断非空 1分 int data