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