《数据结构复习卷部分答案》由会员分享，可在线阅读，更多相关《数据结构复习卷部分答案（5页珍藏版）》请在金锄头文库上搜索。
1、华东华东理工大学理工大学继续继续教育学院教育学院 数据数据结结构构 期中期中试试卷（卷（闭闭卷）卷）班级 学号 姓名 成绩 一一 填空题（共填空题（共 2020 分，每空分，每空 2 2 分）分） 题号 小计 解答 题号 解答1 设 r 指向单链表的某一个结点，要在该结点之后插入数据元素 x，需执行的语句是 s=malloc(size); s-data=x; s-next=r-next ; r-next=s。2 一棵含有 n 个结点的二叉树，它的最小深度为 INT( log2(n)+1 ) 。log 以 2 为底的 n 的对数，加 1 后取整。 3 树有三种常用的存储结构，即孩子链表法，双亲表
2、示法和 孩子兄弟链表法。 4 已知一棵度为 3 的树有 2 个度为 1 的结点，3 个度为 2 的结点，4 个度为 3 的结点，则 该树中有 11 个叶子结点。 一棵度为 M 的树中有 N1 个度为 1 的结点，N2 个度为 2 的结点。 。 。Nm 个度为 m 的结点， 叶子数算法： N0=1+N2+2N3+3N4.(m-1)nm ,就是不考虑度为 1 的结点 5 将一棵有 100 个结点的完全二叉树按层编号，则编号为 49 的结点的双亲编号为 24 。 完全二叉树某一结点 N 的双亲算法：INT(N/2) 6 设 smaxsize为一个顺序存储的栈，变量 top 指向栈顶位置，栈为满的条件
3、是 top=maxsize-1 ，因为 C 语言中 top 指针从 0 开始， 7 一棵哈夫曼树 T，其叶子结点的权分别为 3，16，7，4，11，这棵哈夫曼树的带权路径 长度为 41 。哈夫曼树的带权路径长度规定为所有叶子结点的带权路径长度之和 8 若一棵二叉树的叶子数为 n，则该二叉树中，左、右子树皆非空的结点个数为 n-1 。 同第 4 题，n=1+N2,所以 N2=n-1 9 用 循环 链表存储线性表，可以从表中任一结点出发都能访问到所有结点。 10 设计一个判别表达式中左右括号是否配对的算法，采用 栈 数据结构最佳。二、选择题（共选择题（共 2020 分，每空分，每空 2 2 分）分
4、） 题号小计 选择BADBDD16534BAD1 设有一顺序栈 S，元素 s1，s2，s3，s4，s5，s6依次进栈，如果 6 个元素出栈的顺序是 s2，s3，s4，s6，s5，s1，则栈的容量至少应该是 B 。 A) 2 B) 3 C) 5 D) 6 进栈出栈表如下 ：s1- -s1 s2- s1- s1 s3-s1- s1 s4- s1- s1 s5- s1 s5 s6- s1 s5-s1-0 2 链栈和顺序栈相比，有一个较明显的优点是 A 。 A) 通常不会出现栈满的情况 B) 通常不会出现栈空的情况 C) 插入操作更加方便 D) 删除操作更加方便 链栈可以无限增加下去，3 设森林 T
5、中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n2，n3和 n4，那么 当把森林 T 转换成一棵二叉树后，其根结点的右子树上有 D 个结点。 A) n1-1 B) n1 C) n1+n2+n3 D) n2+n3+n4 森林转换成二叉树，第一棵树变成左子树，其他所有树都连到右子树上，所以右子数上 的结点为后三棵对上所有结点 4 下面关于线性表的叙述错误的是 B D 。 A) 线性表采用顺序存储，必须占用一片地址连续的单元； B) 线性表采用顺序存储，便于进行插入和删除操作； C) 线性表采用链式存储，不必占用一片地址连续的单元； D) 线性表采用链式存储，不便于进行插入和删除操作；
6、 5 设 rear 是指向非空带头结点的循环链表的尾指针，则删除首元结点的操作为 C 。 A） s=rear; rear=rearnext; free(s) B） rear=rearext; free(rear) C） rear=rearnextnext; free(rear) D） s=rearnextnext; rearnextnext=snext; free(s) 6 已知 L 是一单链表，p结点既不是首元结点，也不是尾结点，那么在 p结点后插入 s结 点的语句序列是 1 6 ，删除 p结点的直接后继的语句序列是 534 。 snext=pnext pnext=snext pnext=p
7、nextnext free(q) q=pnext pnext=s 7 深度为 6 的二叉树最多有 B 个结点。A) 64 B) 63 B) 32 D) 31 结点数为 2n -1 8 为了提高内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的存储空间时，应将两栈的 分别设在这片内存空间的两端，这样，只有当 时，才产生上溢。A) 栈底 B）栈顶 C） 两个栈的栈顶同时到达栈空间的中心点 D)两个栈的栈顶在栈空间的某一点相遇栈 底相 遇栈 底三、是非三、是非题题（共（共 10 分）在下面的分）在下面的说说法中，正确的打法中，正确的打()， ，错误错误的打（的打（） ） 题号小计 选择 在二
8、叉树的先序序列中，若结点 u 在结点 v 之前，则 u 一定是 v 的祖先。 在线性表的顺序存储结构中，进行插入和删除运算时，移动元素的个数与该元素在线性 表中的位置有关。 顺序存储结构只能用于存储线性结构，而不能存储非线性数据结构。 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。 一棵二叉树中第 i 层上最大的结点个数为 2i-1个。 二叉树是树的特殊形式。 队列是一个具有后进先出性质的线性数据结构。 串的数据元素类型只能是字符。 若一棵二叉树的先序和后序遍历序列正好相反，则该二叉树一定只有一个结点。 顺序表的存储密度一定比链表的存储密度大。 四、四、应应用用题题（
9、共（共 20 分，每小分，每小题题 5 分）分） 1 设用于通讯的电文仅由 7 个字母组成，字母在电文中出现的频率分别为 3，12，9，6，17，21，32。 请为这 7 个字母设计哈夫曼编码。 （注：写出设计过程） 2 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格 处的内容，并画出该二叉树。 先序序列 ABDFKICEHJG 中序序列 DBKFIAHEJCG 后序序列 DKIFBHJEGCA3 分别用顺序存储结构和链式存储结构画出下图所示二叉树的存储结构。4 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试
10、画出这棵二叉树。 结果：方法说明：由前序 ABECDFGHIJ 可以断定 A 为根结点， 、由中序 EBCDAFHIGJ 可以断定 EB为左子树， 为右子树 、前序 ABECDFGHIJ 中 可以断定 为根结点，由 中序中 可 以定为的左子树，为有右子树 、前序中 和中序中 可以定 为的右子树 、前序中 可以定 为根， 中序中 可以定 左子树为空。 为右子树 、前序中 可以定 为根， 中序 可以定 为左子树， 为的右子树 、前 ，中序 ，可以定 为的右子树。五、算法填空题（共五、算法填空题（共 10 分）分） 1 下面是一个将关键字值插入到二叉排序树中的算法，请在划线处填上正确的语句。type
11、def struct pnode int key; struct node *left, *right; void searchinsert(int x; pnode t) /t 为二叉排序树的根指针 if ( ) p=malloc(size);pkey= ; pleft=NULL;pright= ;t=p; else if (xnext ; pnext=s; temp=pdata; pdata= s-data ; sdata= temp ;六、算法题：（共六、算法题：（共 20 分）分） 1 （7 分）请写一算法，从顺序表中删除具有最小值的元素并由函数返回被删元素的值。 空出的位置由最后一个
12、元素填补，若顺序表为空则显示出错信息并退出运行。 #define MAXSIZE 10 typedef struct stbldatatype elemMAXSIZE;int last;SqlType; 2.（7 分）请编写一算法，在一个按数据元素大小递增的线性链表中插入一个数据元素， 让其仍然保持递增有序。 typedef struct nodedatatype data;struct node *next;Lnode, *Lpointer;3 （6 分）请编写算法求二叉树中度为 1 的结点的个数。typedef struct tnodedatatype data;struct tnode *lc, *rc;btnode, *bitreptr;
