A．front=front+1 B．front=(front+1) mod (m-1) C．front=(front+1) mod m D．front=(front+1)mod(m+1)
10、数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是（ ）。 A. 1175 B. 1180 C. 1205 D. 1210
11、设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）。N=n0+n1+n2+n3+n4=n0+8=16
A．5 B．6 C．7 D．8 N=1+n1+2n2+3n3+4n4=1+4+2*2+3*1+4*1=16
： | | | | | | |
防灾科技学院
2015 ~ 2016 学年 第一学期期中考试
阅卷 数据结构试卷(A) 使用班级 灾害信息工程系14级 答题时间120分钟
题号 一 二 三 四 五 总分 教师 名姓| 装 | | | | ：号|学订 | | | | ：|级班| 线 | | | ：| 号序| 卷试| | |
得分
一、 阅卷教师 得 分 单选题（本大题共 20小题，每题1分，共20分。）
1、从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2、一个算法应该是（ ）。
A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 3、线性表是具有n个（ ）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项 E．信息项
4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表
5、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。
A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表 6、非空的循环单链表head的尾结点p满足（ ）。
A．p->next==head B．p->next==NULL C．p==NULL D．p== head
7、若已知一个栈的入栈序列是1,2,3,.,n，其输出序列为p1,p2,p3，.，pN,若pN是n，则pi是（ ）。
A. i B. n-i C. n-i+1 D. 不确定
8、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 2 3 1 4 5 C. 1 5 4 3 2 D. 5 4 1 3 2 9、循环队列存储在数组A[0..m]中，则出队时的操作为（ ）。
第1页(共3页)
12、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有（ ）结点。A．2h B．2h-1 C．2h+1 D．h+1
13、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）。
A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 14、对于有n 个结点的二叉树, 其高度为（ ）。 A．nlog2n B．log2n C．?log2n?+1 D．不确定 15、树的后根遍历序列等同于该树对应的二叉树的( ).
A. 先序序列 B. 中序序列 C. 后序序列 D. 层序序列 16、在下述结论中，正确的是（ ）。
①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．①②③ B．②③④ C．②④ D．①④
17、具有9个叶结点的二叉树中有（ ）个度为2的结点。 A．8 B．9 C．10 D．ll
18、二叉树的第I层上最多含有结点数为（ ）。 A．2I B．2I-1-1 C．2I-1 D．2I -1
19、递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表 20、有n个叶子的哈夫曼树的结点总数为（ ）。 A．不确定 B．2n C．2n+1 D．2n-1
选择题请将答案填写在下面的表格中。
1-5 CBCAD 6-10 ADDDA 11-15 DBADB 16-20 DACCD
| | | | | |
装
（ √ ）9、树与二叉树是两种不同的树型结构。
阅卷教师 得 分 二、
填空题（本大题共9小题，每空2分，共20分。）
（ √ ）10、一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
阅卷教师 得 分 四、 应用题（本大题共6小题，共35分。）
1、下面程序段的时间复杂度为________。(n>1) O(n) sum=1；
for (i=0;sum 2、对于一个具有n个结点的单链表，在已知指针p指向的结点后插入一个新结点的时间复1、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点? (5分) 答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当：名姓| | | | | 订 ：|号学| | | | | 线 ：级|班 | | | | | ：号| 序卷| 试| | | 杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。O(1)，O(n) 3、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动________个元素。n-i+1 4、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。顺序 5、在单链表p结点之后插入s结点的操作是：_______。s->next=p->next;p->next=s; 6、在单链表L中，指针p所指结点有后继结点的条件是：__ p->next!=NULL 7、一棵深度为10的二叉树最多有 个结点。210-1=1023 8、已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多 是 个 235 9、一棵二叉树中的结点的度或为0或为2，其中n0是度为0的结点的个数，则二叉树的枝数为 。 2(n0-1) 三、 阅卷教师 判断题（本大题共10小题，每题1分，共10分。） 得 分 （ × ）1、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ × ）2、对任何数据结构链式存储结构一定优于顺序存储结构。 （ √ ）3、栈是实现过程和函数等子程序所必需的结构。 （ √ ）4、栈和队列都是限制存取点的线性结构。 （ √ ）5、循环队列也存在空间溢出问题。 （ × ）6、特殊矩阵压缩存储后，必会失去随机存取功能。 （ × ）7、对一棵二叉树进行层次遍历时，应借助于一个栈。 （ √ ）8、给定一棵树，可以找到唯一的一棵二叉树与之对应。 第2页(共3页) 前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。 2、设输入元素为1、2、3、P和A，输入次序为123PA，如图（编者略）。元素经过栈后达输出序列，当所有元素均到达输出序列后，有哪些序列可以作为C语言的变量名。并写出入栈和出栈的过程。(5分) 答：一般说，C语言的变量名是以字母开头的字母数字序列。故本题答案是: AP321,PA321,P3A21,P32A1,P321A。 ： | | | | | | 装 3、试推导证明在一棵具有n个结点的二叉树中，如果采用二叉链表存储结构，则有n+1个空指针。(5分) 2n -（n-1）= n+1 4、由二叉树的中序遍历序列及后序遍历序列能唯一的建立二叉树，已知二叉树的中序遍历序列DBEAFGC和后序遍历序列DEBGFCA，试求出以下问题： (1) 试构造二叉树(3分) 五、 阅卷教师 得 分 算法设计题（本大题共2小题，共15分。） 1、假设某个单向循环链表中，各元素均为字符型，其长度大于1，且表中既无头结点也无头指针。已知p为指向链表中某个结点的指针，试编写算法完成如下操作： 在链表中删除指针p所指结点的直接前驱结点,将结点值用变量x返回，并释放删除结点，函数DataType ListDelete (LNode *p)。(5分) | 名姓| | | | 订 | ：号|学| | | | 线 ：|级班| | | | | ：| 号序| 卷试| (2) 给出先序遍历序列；(2分) (3) 画出由该二叉树对应的森林。(3分) 5、假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的频度分别为{0.31,0.16,0.10,0.08,0.11,0.20,0.04}，试求出以下问题： (1) 用○表示叶子结点，用□表示分支结点，构造相应的huffman树；(3分) (2) 计算它的带权路径长度；(2分) (3) 写出它的huffman编码；(3分) 6、写出右图的中序遍历序列，并画出其中序线索二叉树。(4分) 第3页(共3页) DataType ListDelete (LNode *p) { Q=p; While(q->next->next!=p) q=q->next; R=q->next; X=r->data; q->next=p; free(r); return x; } 2、设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。要求不用另外的数组或结点完成. 各结点的结构体类型如下： typedef int DataType; // DataType为线性表的数据类型 typedef struct LNode { DataType data; // 数据域 struct LNode *next; // 指针域 } LNode; LNode *first;//first为该链表的头指针 请采用void invert(LNode *first)为函数头将题目算法给出void invert(LNode *first)∥first是 带头结点且数据项递减有序的单链表，本算法将其排列成数据项递增有序的单链表。 {p=first->next； // p=first->next->next；/*p为工作指针*/ first ->next=null；// first ->next->next=null； while（p!=null） {s=p; p=p->next; /*暂存链头结点，p后移。*/ s->next= first->next；/*将s结点前插入头结点后。*/