数据结构考试试题.doc

数据结构辅导试题一一 、简答问题：1 四类数据结构2 线性结构与非线性结构有何差别？3 简述算法的定义与特性。4 设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打r 。 1 （ ）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。2 （ ）索引顺序表的特点是块内可无序，块间要有序。3 （ ）子串是主串中任意个连续字符组成的序列。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. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：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中，指针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，请用快速排序，写出第一趟排序结果。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分）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. 链域数目不同 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解答：int 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!=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. 简述参数传递的主要方式及其特点。二、判断正误：（每小题1分，共5分）正确在（ ）内打，否则打r 。 ( )（1）在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。( )（2）在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。( )（3）在一个小根堆中，具有最大值的元素一定是叶结点。( )（4）索引顺序表的特点是块间可无序，但块内一定要有序。( )（5）哈夫曼树中没有度为1的结点，所以必为满二叉树。三、单项选择题：(每小题1分，共5分)1对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为:A) 顺序表 B) 用头指针表示的单循环链表C) 用尾指针表示的单循环链表 D) 单链表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）求两个指向结点间的最短路径，其结果必定是唯一的（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的最大值是: 。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，子链表最后一个结点的地址为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，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 指向根结点。编写算法，逐层遍历这棵树。 10分数据结构试卷参考答案一、简答题：（每小题3分，共15分）1. 前驱与后继之间通常为一对多或多对多的关系。2. 顺序表优点：随机查找，存储密度大顺序表缺点：插入、删除不便，静态分配，表长固定单链表优点：插入、删除方便，动态分配，表长灵活单链表缺点：查找不便，存储密度小3. 关键字相同的两个记录，排序前后其先后顺序不变。4. typedef struct nodeElemType data;struct node * next; *LinkStack;5. 当二叉排序树接近平衡二叉树或完全二叉树时查找性能较好，当二叉排序树为单边单枝二叉树时查找性能最差。二、判断正误：（每小题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分）123或： WPL=83+44+54+162+93+123+262 =207注：哈夫曼树的左右子树可以互换。4解1：解2：注：边上的权值可以省略。5初始堆：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-next=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. 说明以下三个概念的关系：头指针，头结点，首元素结点。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）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的逻辑特性，不必考虑如何在计算机中实现。( )（7）数组元素的下标值越大，存取时间越长。( )（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。( )（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。( )（10）长度为1的串等价于一个字符型常量。三、单项选择题（10分, 每小题1分）1排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？ A、堆排序B、直接插入排序C、快速排序D、冒泡排序2 已知一个有向图的邻接矩阵表示，要删除所有从第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) 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将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为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 high ) 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 分）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。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下查找成功的平均查找长度。3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53， 87）调整为大根堆。4（4分）已知权值集合为： 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 = NULL; 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 无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分）3 编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）数据结构试卷参考答案一、简答题（15分，每小题3分）1. 算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。2. 主要与哈希函数、装填因子有关。如果用哈希函数计算的地址分布均匀，则冲突的可能性较小，如果装填因子较小，则哈希表较稀疏，发生冲突的可能性较小。3. 图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。4. 头指针指向头结点，头结点的后继域指向首元素结点。5. 当队尾到达数组最后一个单元时，就认为队满，但此时数组前面可能还有空单元，因此叫假溢出。解决的方法是采用循环队列，即令最后一个单元的后继是第一个单元。二、判断题（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 )