《数据结构期中练习及参考答案》由会员分享，可在线阅读，更多相关《数据结构期中练习及参考答案（5页珍藏版）》请在金锄头文库上搜索。
1、1数据结构中期练习1、判断题 请在题后括号内打上“T” （正确）或“F” （错误）1在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。 （ F ）2. 在对带头结点的链队列作出队操作时，头指针的值不会改变。 （ T ）头结点3用 S 表示入栈操作， X 表示出栈操作，若元素入栈顺序为 1,2,3,4, 为了得到1,3,4,2 出栈顺序相应的 S 和 X 操作序列为 SXSSXSXX。 （ T ）4. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 （ T ）5. 顺序存储的线性表可以按序号随机存取。( T )链式表是按顺序连续存储6. 带头结点
2、的单链表队列，头指针 F 指向队列的头结点，尾指针 R 指向队列的最后一个结点（ F ） 空队列7空串是由空白字符组成的串。 （ F ）8字符串比较ABCDEFGABF的结果为 （ F ）9顺序栈插入、删除操作都是在同一端的进行，该端称为堆底。 （ F ）10给定循环链表中任一元素的地址均可得到其直接前驱的地址（ T ）二、单选题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ A ）以及它们之间的关系和运算等的学科。A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映象2. 设单链表中指针 p 指向结点 m ，若要删除 m 之后的结点（若存在） ，则需修改指针的操作为（
3、 A ） 。A.q=p-next;p-next=p-next-next;free(q); B. p=p-next;C. p=p-next-next; D. p-next=p;3. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表(经过最少的结点)4下面程序段的时间复杂度是( B )。for (i=1;inext = = NULL;C. head-next = = head; D. head! = NULL;6. 在循环双链表的 p 所指结点之后
4、插入 s 所指结点的操作是 ( D )。A. p-right=s; s-left=p; p-right-left=s; s=-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right= p-right; p-right=s; p-right-left=s;D. s-left=p; s-right=p-right; p-right-left=s; p-right=s;27假设顺序栈的定义为：typedef struct selemtype *base; /* 栈底指针*/s
5、elemtype *top; /* 栈顶指针*/int stacksize; /* 当前已分配的存储空间,以元素为单位*/sqstack;变量 st 为 sqstack 型，则栈 st 为满的判断条件为（ C ） 。A st.base = NULL B st.top = st.stacksizeC st.top-st.base= st.stacksize D st.top = st.base8判断一个循环队列 QU ( m0为最大队列长度(以元素为单位)，front 和 rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( A )。AQU-front = QU-rear BQU-fr
6、ont != QU- rearCQU-front = (QU-rear+1) % m 0 DQU-front != (QU-rear+1) % m 0三、算法设计题 1.假设称正读和反读都相同的字符序列为“回文” (即回文是指一个字符序列以中间字符为基准两边字符完全相同)，例如， abba和abcba是回文，ababab则不是回文。试编写一个判断读入的一个以为结束符的字符序列是否“回文”的算法。解题思路：判断回文算法 Palindrome_Test()的思想是：把字符串中的字符逐个分别存入队列和堆栈，然后逐个出队列和退栈并比较出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列是回
7、文，否则就不是回文。实现本题功能的函数如下(类 C 编写)：int Palindrome_Test() /判别输入的字符串是否是回文序列，是则返回 1，否则返回 0 Initstack(S); InitQueue(Q);while ( (c =getchar() !=)Push(S,c); EnQueue(Q,c); /同时使用栈和队列两种结构while(!StackEmpty(S)Pop(S,a); DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test2.已知 Q 是一个非空队列，S 是一个空栈。仅用队列和栈的基本操作函数
8、和少量工作变量，编写一个算法，将队列 Q 中的所有元素逆置。 栈的基本操作函数有： clearstack( 置空栈 push( 新元素 e 进栈 pop(s,&e):出栈，返回栈顶值给 e stackEmpty(s): 判栈空否 3队列的基本操作函数有 enqueue( 元素 e 进队 dequeue(&q,&e):出队列，返回队头值给 e queueempty(q): 判队列空否aaa(q,s)clearstack(s)while(!queueempty(q)dequeue(q,e);删除队尾元素，返回 e。push(s,e);while(!stackempty(s) pop(s,e);en
9、queue(q,e);插入队头元素 e设在树中，结点 x 是结点 y 的双亲时，用(x,y)来表示树变。已知一棵树边的集合为： (i,m),(i,n),(b,e),(e,i),(b,d),(a,b),(g,j),(g,k),(c,g),(c,f),(h,l),(c,h),(a,c)用树形表示法画出此树，并回答下列问题：（1） 哪个是根结点？2）哪些是叶结点？3）哪个是 g 的双亲？4）哪些是 g 的祖先？5） 哪些是 g 的孩子？6）哪些是 e 的子孙？7）哪些是 e 的兄弟？哪些是 f 的兄弟？8） 结点 b 和 n 的层次各是多少？9）树的深度是多少？10）以结点 c 为根的子树的深度是多
10、少？11）树的度数是多少？答案：（1） a 是根结点。2）d,m,n,j,k,l,f 是叶结点。3）c 是 g 的双亲。4）a,c 是 g 的祖先。5） g 的孩子是 j,k.。6）e 的子孙是 i,m,n.。7）e 的兄弟是 d,f 的兄弟是 g,h。8）b 在第二层,b 在第五层。9）树的深度为 5。10）以 C 为根的子树的深度为 3。11）树的度数为3。2、分别写出上图所示二叉树的的先序、中序、后序、层序遍历的序列。4先序：ABECDFGHIJ中序：EBCDAFHIGJ后序：EDCBIHJGFA层序：ABFECGDHJI2对于如图所示的森林，要求：(1)将其转换为相应的二叉树；(2)写
11、出该森林的先序遍历序列和中序遍历序列。(1)该森林所对应的二叉树如下图所示：(2)该森林的先序遍历序列为：ABDEFCGHIJKL，中序遍历序列为：DEFBCAHIJGLK。1、已知一棵二叉树的前序遍历的结果序列是 ABECDFGHIJ, 中序遍历的结果序列是EBCDAFHIGJ, 试画出这棵二叉树。答案：2、试找出分别满足下列条件的所有二叉树：（1）先根序列和中根序列相同；（2）后根序列和中根序列相同；（3）先根序列和后根序列相同；答案：（1）空二叉树或仅有一个结点的非空二叉树或任一结点均无左子树的非空二叉树（2）空二叉树或仅有一个结点的非空二叉树或任一结点均无右子树的非空二叉树AB CD
12、E FGIH JKLAB GD C H KEFIJL5（3）空二叉树或仅有一个结点的非空二叉树设有一段正文是由字符集A,B,C,D,E,F组成的，正文长度为 100 个字符，其中每个字符要正文中出现的次数分别为 17,12,5,28,35,3。若采用哈夫曼编码对这段正文进行压缩存储，请完成如下的工作：(1)构造哈夫曼树(规定权值较小的结点为左子树 )；(2)写出每个字符的哈夫曼编码；(3)若有某一段正文的二进制编码序列为 01101010110011，请按(2) 的哈夫曼编码将它翻译成所对应的正文。解：(1)在这段正文中，每个字符出现的次数相当于每个字符的出现频率，根据哈夫曼树的构造方法，可建造哈夫曼树如下图所示。A D EBF C(2)各个字符的哈夫曼编码分别为：A：00 B：011 C：0101 D：10 E：11 F：0100(3)若将二进制序列 01101010110011 从开头开始，依次分解为所对应的字符编码，即： 011 0101 011 00 11，则所对应的字符序列为 BCBAE。1210037 6317 20 28 3583 5
