数据结构考试试题(14页).doc

《数据结构考试试题(14页).doc》由会员分享，可在线阅读，更多相关《数据结构考试试题(14页).doc（14页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构考试试题-第 14 页数据结构辅导试题一一 、简答问题：1 四类数据结构2 线性结构与非线性结构有何差别？3 简述算法的定义与特性。4 设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打r 。 1 （ ）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。2 （ ）索引顺序表的特点是块内可无序，块间要有序。3 （ ）子串是主串中任意个连续

2、字符组成的序列。4 （ ）线性结构只能用顺序结构存放，非线性结构只能用链表存放。5 （ ）快速排序的枢轴元素可以任意选定。三、单项选择题：(每小题1分，共4分)1栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C2将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、483. 对下列关键字序列用快速排序法进行排序时

3、，速度最快的情形是：A）21、25、5、17、9、23、30 B）25、23、30、17、21、5、9B）21、9、17、30、25、23、5 D）5、9、17、21、23、25、304. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是：A）M1 B）M1+M2 C）M3 D）M2+M3四、填空题：(每小题2分,共 20分)1 设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（Pnext= 和p-next= 的操作.8广义表(a,b),c,d)的表头是 ,表尾是 9循环单链表LA中，指针

4、P所指结点为表尾结点的条件是 10在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用 排序方法最好。五、构造题：（每小题5分，共25分）1 已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2 设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。3 有一组关键字50，52，85，22，96，17，36，55，请用快速排序，写出第一趟排序结

5、果。4 已知叶子结点值2，3，5，6，9，11，构造哈夫曼树，计算其带权路径长度。5 画出8个结点的折半判定树。六、算法设计题：（每小题15分，共30分）（仅要求给出子程序）1编写算法，判断带头结点的双向循环链表L是否对称。（15分）对称是指：设各元素值a1,a2,.,an, 则有ai=an-i+1 ，即指：a1= an，a2= an-1 。 结点结构为：priordatanext2 二叉排序树T用二叉链表表示，其中各元素均不相同。（1） 写出递归算法，按递减顺序打印各元素的值。（10分）（2） 写出完成上述要求的非递归算法。（5分）数据结构试卷参考答案一 、简答问题：（每小题4分，共16分）

6、1 集合结构、线性结构、树形结构、网状结构2 线性结构的前驱与后继之间为一对一关系，非线性结构的前驱与后继之间通常为一对多或多对多关系。3 解决特定问题的有限指令序列。有限性、确定性、可行性、有0个或多个输入数据、有1个或多个输出结果。4 堆排序。因为一趟堆排序排定一个元素，只需进行前10趟堆排序就可以了。其它排序方法均需进行完全排序。二、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打r 。 1.（r） 2.（） 3.（） 4.（r） 5.（）三、单项选择题：(每小题1分，共4分)1C) 2A) 3. A) 4. D)四、填空题：(每小题2分,共 20分)1 97 2. n+1 3.

7、 链域数目不同 4. 哈希查找法 5. 26 1 6. 1168 7. p-next 、 s 8.(a,b) 、 (c,d) 9. P-next=LA 10. 直接插入 五、构造题：（每小题5分，共25分）1 2 012345678910KTABAMDCIXTNIASL=20/9012345678910ASL=15/93 36，17，22，50，96，85，52，554 WPL=112+62+92 +53 +24+34 =87注：哈夫曼树的左右子树可以互换。5 注：如果求中点时采用向上取整，则二叉树的形态为左子树偏长。六、算法设计题：（每小题15分，共30分） （仅要求给出子程序）1解答：in

8、t judge(DLinkList L)p=L-next; q=L-prior;while(p!=q) if(p-data!=q-data) return 0;if(p-next=q) return 1;p=p-next;q=q-prior;return 1;注：可以不用返回值，而用打印信息。2 解答：（1）void print_1(BiTree T)if(T!=NULL) print_1(T-RChild); printf(“%c”, T-data); print_1(T-LChild);（2）void Print_2（BiTree T） InitStack (&S);p=T;while(p

9、!=NULL | ! IsEmpty(S) while (p!=NULL) Push(&S, p);p=p-RChild;if ( ! IsEmpty(S) ) Pop(&S, &p); printf (“%c”, p - data ); p = p - LChild; 数据结构辅导试题二一、简答题：（每小题3分，共15分）1. 什么情况下二叉排序树的查找性能较好？什么情况下二叉排序树的查找性能最差？2. 比较顺序表与单链表的优缺点。3. 请写出栈的链式存储结构的类型定义。4. 在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。5. 简述参数传递的主要方式

10、及其特点。二、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打r 。 ( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。三、单项选择题：(每小题1分，共5分)1对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:A) 顺序表 B) 用头指针表示的单循环链表C) 用尾指针表示的单循环链表 D) 单

11、链表2假设以第一个元素为分界元素，对字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）进行快速排序，则第一次划分的结果是：A) (A, C, D, F, H, M, P, Q, R, S, X, Y) B) (A, F, H, C, D, P, M, Q, R, S, Y, X) C) (F, H, C, D, P, A, M, Q, R, S, Y, X) D) (P, A, M, F, H, C, D, Q, S, Y, R, X)3下面是三个关于有向图运算的叙述：（1）求有向图结点的拓扑序列，其结果必定是唯一的（2）求两个指向结点间的最短路径，其结果必定是唯

12、一的（3）求AOE网的关键路径，其结果必定是唯一的其中哪个（些）是正确的？A) 只有（1） B) （1）和（2） C) 都正确 D) 都不正确4若进栈序列为a, b, c，则通过入出栈操作可能得到的a, b, c的不同排列个数为:A) 4 B) 5 C) 6 D) 75. 以下关于广义表的叙述中,正确的是：A) 广义表是由0个或多个单元素或子表构成的有限序列B) 广义表至少有一个元素是子表C) 广义表不能递归定义 D) 广义表不能为空表四、填空题：(每小题2分,共 20分)1 一棵含有101个结点的完全二叉树存储在数组A1.101中, 对1k101, 若Ak是非叶结点, 则k的最小值是: ，k

13、的最大值是: 。2. 设s=YOU ARE JUDGING IT RIGHT OR WRONG，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2); 则最后sub1的值为： 。3. 若一个算法中的语句频度之和为T(n) = 3720n+4nlogn，则算法的时间复杂度为_ 。4广义表(a),b),c),d)的表头是 ，表尾是 。 5 已知有向图的邻接矩阵，要计算i号结点的入度，计算方法是：将 累加。6要在一个单链表中p所指结点之后插入一个子链表，子链表第一个结点的地址为s，子链表最后一个结点的地址为

14、t, 则应执行操作： 和 。7. 用带头结点的循环链表表示的队列,若只设尾指针rear, 则队空的条件是 。8已知二维数组A1020采用行序为主方式存储，每个元素占2个存储单元,并且A00的存储地址是1024, 则A618的地址是 9在表示二叉树的二叉链表中,共有 个空链域。10 n个顶点的连通无向图至少有 条边，至多有 条边。五、构造题：（每小题6分，共30分）1已知二叉树的中序序列为DBGEAFC，后序序列为DGEBFCA，给出对应的二叉树。2已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素均为1。请画出该图，并给出其邻接表。3给定权值8，12，

15、4，5，26，16，9，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。4图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。图25对关键字序列 (72，87，61，23，94，16，05，58) 进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和一趟排序后的序列状态。六、算法设计题：（共25分）1 设有一个由正整数组成的单链表L（含头结点），编写完成下列功能的算法： 找出最小值结点P， 若最小值是奇数，则删除结点P。15分2 已知树用孩子兄弟链表存储，root 指向根结点。编写算法，逐

16、层遍历这棵树。 10分数据结构试卷参考答案一、简答题：（每小题3分，共15分）1. 前驱与后继之间通常为一对多或多对多的关系。2. 顺序表优点：随机查找，存储密度大顺序表缺点：插入、删除不便，静态分配，表长固定单链表优点：插入、删除方便，动态分配，表长灵活单链表缺点：查找不便，存储密度小3. 关键字相同的两个记录，排序前后其先后顺序不变。4. typedef struct nodeElemType data;struct node * next; *LinkStack;5. 当二叉排序树接近平衡二叉树或完全二叉树时查找性能较好，当二叉排序树为单边单枝二叉树时查找性能最差。二、判断正误：（每小题

17、1分，共5分）正确在（ ）内打，否则打r 。 (r)（1） (r)（2） ()（3） (r)（4） (r)（5）三、单项选择题：(每小题1分，共5分)1C) 2C) 3D) 4B) 5. A) 四、填空题：(每小题2分,共 20分)1 1 2. YOU ARE RIGHT 3. O(nlogn) 4 (a),b),c) ， (d) 5 i列元素 6 t-next=p-next ， p-next=s 7. rear-next=rear 8 1300 9 n+1 10 n-1 五、构造题：（每小题6分，共30分）或： WPL=83+44+54+162+93+123+262 =207注：哈夫曼树的左

18、右子树可以互换。解1：解2：注：边上的权值可以省略。初始堆：05，23，16，58，94，72，61，87一趟排序后的序列状态：87，23，16，58，94，72，61，05筛成堆后为：16，23，61，58，94，72，87，05注：如果采用大根堆，应适当减分。六、算法设计题：（共25分）3 15分void min(LinkList L)if(L-next=NULL) return;q=L; r=L-next; m=r-data;while(r-next!=NULL) if(r-next-datanext-data; q=r; r=r-next;p=q-next;if(m%2=1) q-ne

19、xt=p-next; free(p); 4 10分void layer(CSTree root)InitQueue(&Q); EnterQueue(&Q, root);while(!Empty(Q) DelQueue(&Q, &p); visit(p); p=p-FirstChild; while(p!=NULL) EnterQueue(&Q, p); p=p-NextSibling; 数据结构辅导试题三一、简答题（15分，每小题3分）1. 简要说明算法与程序的区别。2. 在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3. 说明在图的遍历中，设置访问标志数组的作用。4. 说明以下三个概念

20、的关系：头指针，头结点，首元素结点。5. 在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？二、判断题（10分，每小题1分） 正确在括号内打，错误打( )（1）广义表( a ), b), c ) 的表头是( a ), b)，表尾是( c )。( )（2）在哈夫曼树中，权值最小的结点离根结点最近。( )（3）基数排序是高位优先排序法。( )（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。( )（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面 ：p-next = s; s-next = p-next;( )（6）抽象数据类型（ADT）包括定义和

21、实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( )（7）数组元素的下标值越大，存取时间越长。( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。( )（10）长度为1的串等价于一个字符型常量。三、单项选择题（10分, 每小题1分）1排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序B、直接插入排序C、快速排序D、冒泡排序2 已知一个有

22、向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应该：A）将邻接矩阵的第i行删除 B）将邻接矩阵的第i行元素全部置为0C）将邻接矩阵的第i列删除 D）将邻接矩阵的第i列元素全部置为03有一个含头结点的双向循环链表，头指针为head, 则其为空的条件是：A. head-priro=NULL B. head-next=NULL C. head-next=head D. head-next- priro=NULL4. 在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为： A) 2 B) 3 C)

23、4 D) 55. 以下哪一个不是队列的基本运算？A）从队尾插入一个新元素 B）从队列中删除第i个元素 C）判断一个队列是否为空 D）读取队头元素的值6. 在长度为n的顺序表的第i个位置上插入一个元素（1 i n+1），元素的移动次数为：A) n i + 1 B) n i C) i D) i 1 7对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:A) 顺序表 B) 用头指针表示的循环单链表C) 用尾指针表示的循环单链表 D) 单链表8对包含n个元素的哈希表进行查找，平均查找长度为：A) O(log2n) B) O(n) C) O(nlog2n) D) 不直接依赖于n9将一棵有10

24、0个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为： A、48B、49C、50D、5110某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：A）3 B）2 C）4 D）5四、填空题（10分，每空1分）1填空完成下面一趟快速排序算法：int QKPass ( RecordType r , int low， int high) x = r low ； while ( low high )while ( low = x.key ) high - -；if ( low hig

25、h ) r = r high ； low+; while ( low high & r . key x. key ) low+;if ( low high ) r = r low ； high-; r low = x； return low ; 2. 假设用循环单链表实现队列，若队列非空，且队尾指针为R, 则将新结点S加入队列时，需执行下面语句： ； ；R=S；3通常是以算法执行所耗费的 和所占用的 来判断一个算法的优劣。4已知一个3行、4列的二维数组A（各维下标均从1开始），如果按“以列为主”的顺序存储，则排在第8个位置的元素是： 5高度为h的完全二叉树最少有 个结点。五、构造题（20 分）

26、1（4分）已知数据结构DS的定义如下，请给出其逻辑结构图示。DS = (D, R)D = a, b, c, d, e, f, g R = T T = , , , , , , , , , , , 2（6分）对以下关键字序列建立哈希表：（SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函数为H(K) =（K中最后一个字母在字母表中的序号）MOD 7。用线性探测法处理冲突，要求构造一个装填因子为的哈希表，并计算出在等概率情况下查找成功的平均查找长度。3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53， 87）调整为大根堆。4（4分）已知权值集合为：

27、 5，7，2，3，6，9 ，要求给出哈夫曼树，并计算其带权路径长度WPL。六、算法分析题（10分）阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。（1） 简要说明程序功能。（5分）（2） n个结点的满二叉树的深度h是多少？（3分）（3） 假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间复杂度。（2分）int Proc (BSTree *bst, KeyType K) BSTree f, q, s;s=(BSTree)malloc(sizeof(BSTNode); s- key = K; s- lchild = NULL; s- rchild = NU

28、LL; if ( *bst = NULL ) *bst = s; return 1; f = NULL; q = *bst; while( q != NULL ) if ( K key ) f = q; q = q - lchild; else f = q; q = q - rchild; if ( K key ) f - lchild = s; else f - rchild = s; return 1; 七、算法设计题（25分）1 已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）2 无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点

29、序列。（8分）3 编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）数据结构试卷参考答案一、简答题（15分，每小题3分）1. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。2. 主要与哈希函数、装填因子有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子较小，则哈希表较稀疏，发生冲突的可能性较小。3. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。4. 头指针指向头结点，头结点的后继域指向首元素结点。5. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此

30、叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。二、判断题（10分，每小题1分）（1）() （2）() （3）() （4）() （5）()（6）() （7）() （8）() （9）() （10）()三、单项选择题（10分, 每小题1分）1 D） 2 B） 3 C） 4. C） 5. B）6. A) 7 C) 8 D) 9 C） 10C） 四、填空题（10分，每空1分）1 high low low high 2. S-next=R-next ； R-next=S ；3 时间 空间 4 A2, 3 5 2h-1 五、构造题（20 分）1（4分）2（6分）SUNMONTHUFRIWEDTUESAT0123456789ASLsucc = ( 14 + 22 + 3 ) / 7 = 11 / 73.（6分）4（4分）已知权值集合为： 5，7，2，3，6，9 ，要求给出哈夫曼树，并计算其带权路径长度WPL。WPL = 2( 9 + 6 + 7 ) + 35 + 4( 2 + 3 ) = 79 六、算法分析题（10分）解：（1） 在二叉排序树中插入关键字为K的结点（2） h = log2 ( n+1 ) 或 h = log2 n + 1 （方括号表示向下取整）（3） O ( log2 ( n+1 ) ) 或 O ( log2 n )