数据结构复习卷部分答案.doc

华东理工大学继续教育学院
《数据结构》期中试卷（闭卷）

班级学号姓名成绩

一填空题（共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的结点，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设s[maxsize]为一个顺序存储的栈，变量top指向栈顶位置，栈为满的条件是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设计一个判别表达式中左右括号是否配对的算法，采用栈数据结构最佳。

二、选择题（共20分，每空2分）
题号①②③④⑤⑥⑦⑧⑨⑩小计选择BADBDD16
534BAD1设有一顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素出栈的顺序是s2，s3，s4，s6，s5，s1，则栈的容量至少应该是B。
A)2B)3C)5D)6
进栈出栈表如下：s1---s1s2--s1--s1s3--s1--s1s4---s1--s1s5--s1s5s6--s1s5--s1--0
2链栈和顺序栈相比，有一个较明显的优点是A。
A)通常不会出现栈满的情况B)通常不会出现栈空的情况
C)插入操作更加方便D)删除操作更加方便
链栈可以无限增加下去，
3设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1，n2，n3和n4，那么当把森林T转换成一棵二叉树后，其根结点的右子树上有D个结点。
A)n1-1B)n1C)n1+n2+n3D)n2+n3+n4
森林转换成二叉树，第一棵树变成左子树，其他所有树都连到右子树上，所以右子数上的结点为后三棵对上所有结点
4下面关于线性表的叙述错误的是BD。
线性表采用顺序存储，必须占用一片地址连续的单元；
线性表采用顺序存储，便于进行插入和删除操作；
线性表采用链式存储，不必占用一片地址连续的单元；
D)线性表采用链式存储，不便于进行插入和删除操作；
5设rear是指向非空带头结点的循环链表的尾指针，则删除首元结点的操作为C。
s=rear;rear=rear→next;free(s)
rear=rear→ext;free(rear)
rear=rear→next→next;free(rear)
s=rear→next→next;rear→next→next=s→next;free(s)
6已知L是一单链表，p^结点既不是首元结点，也不是尾结点，那么在p^结点后插入s^结点的语句序列是16，删除p^结点的直接后继的语句序列是534。
s→next=p→next
p→next=s→next
p→next=p→next→next
free(q)
q=p→next
p→next=s
7深度为6的二叉树最多有B个结点。
A)64B)63B)32D)31
结点数为2n-1
8为了提高内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的存储空间时，
应将两栈的⑨分别设在这片内存空间的两端，这样，只有当⑩时，才产生上溢。
A)栈底B）栈顶C）两个栈的栈顶同时到达栈空间的中心点
D)两个栈的栈顶在栈空间的某一点相遇

栈底

相遇

栈底
三、是非题（共10分）在下面的说法中，正确的打(√)，错误的打（×）
题号①②③④⑤⑥⑦⑧⑨⑩小计选择×√√×√×√√××①在二叉树的先序序列中，若结点u在结点v之前，则u一定是v的祖先。
②在线性表的顺序存储结构中，进行插入和删除运算时，移动元素的个数与该元素在线性表中的位置有关。
③顺序存储结构只能用于存储线性结构，而不能存储非线性数据结构。
④