长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(C卷)
班级:___________学号:___________姓名:___________得分:___________
题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 成绩 复核 题目部分，(卷面共有32题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分)
1．分析下列程序段的时间复杂度： （1）for (i=1; i<=n; i=2*i) ++x;
（2）for (i=1; i<=n; ++i) for (j=1; j<=i-1; ++j) ++x;
2．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。
二、判断正误(5小题,共10分)
1．顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（ ） 2．非空的双向循环链表中任何结点的前驱指针均不为空。（ ） 3．在循环队列中无溢出现象。（ ）
4．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
5．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ） 三、单项选择题(10小题,共20分)
1．递归算法一般需要利用（ ）实现。
2．已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ ）。
A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m
3．在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（ ）。 A．已固定 B．不固定 C．可以改变 D．动态变化
4．设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（ ）。 A top=top+1; B top=top-1; C top->next=top; D top=top->next; 5．若串S=\，其子串的数目最多是：（ ） 。 A．35 B．36 C．37 D．38
6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（ ）。
A h B h+1 C h或h+1 D 任意 7．下列命题正确的是（ ）。
A 一个图的邻接矩阵表示是唯一的，邻接表表示也唯一 B 一个图的邻接矩阵表示是唯一的，邻接表表示不唯一 C 一个图的邻接矩阵表示不唯一的，邻接表表示是唯一 D 一个图的邻接矩阵表示不唯一的，邻接表表示也不唯一
8． 设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（ ）。 A 99 B 97 C 91 D 93
9．堆的形状是一棵（ ）。
A二叉排序树 B满二叉树 C完全二叉树 D 判定树
10．设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。
A F，H，C，D，P，A，M，Q，R，S，Y，X B P，A，C，S，Q，D，F，X，R，H，M，Y C A，D，C，R，F，Q，M，S，Y，P，H，X D H，C，Q，P，A，M，S，R，D，F，X，Y
四、算法设计题(4小题,共32分)
1．设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
2．设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。 3． 对给定的带头结点的单链表L， 编写一个删除L中值为X的结点的直接前趋结点的算法。4．设计一个在链式存储结构上统计二叉树中结点个数的算法。
五、填空题(11小题,共22分)
1．已知顺序栈S，在对S进行进栈操作之前首先要判断（ ），在对S进行出栈操作之前首先要判断（ ）。
2．设循环队列存放在向量sq.data[0:M]中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 3．广义表((a), (((b),c)),(d))的表头是（ ），表尾是（ ）。 4．在有n个叶子的哈夫曼树中，叶子结点总数为（ ），分支结点总数为（ ）。
5．一棵二叉树的第i（i≥1）层最多有（ ）个结点；一棵有n（n>0）个结点的满二叉树共有（ ）个叶子结点和（ ）个非终端结点。 6．希尔排序法属于（ ）
7．对n个待排序记录序列进行快速排序，所需要的最好时间复杂度是（ ），最坏时间复杂度是（ ）。
8．假设线性表的长度为n，则在最坏情况下，冒泡排序需要的比较次数为（ ） 9．对于键值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从键值为（ ）的结点开始。
10．图形结构的元素之间存在（ ）的关系。 11．数据的存储结构是指（ ）
长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(C卷)
答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共22分) 1．O(log2n) （2）O(n2)
2．【解答】构造的哈夫曼树如图所示。
树的带权路径长度为：
WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120
二、判断正误(5小题,共22分) 1．错 2．对 3．错 4．对 5．对
三、单项选择题(10小题,共22分) 1．栈 2．A 3．A 4．D 5．C 6．C 7． B 8．B 9．C 10．D
四、算法设计题(4小题,共22分)
1．typedef char datatype;
typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) {
lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) {
head=p->next; p->next=0;
if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}
else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } }
2．typedef struct node { int data;
struct node *next; }lklist;
void intersection(lklist *ha,lklist *hb,lklist *&hc) {
lklist *p,*q,*t; For(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next)
if (q->data==p->data) break; if(q!=0){
t=(lklist *)malloc(sizeof(lklist)); t->data=p->data; t->next=hc; hc=t;} } }
3．解：
void delete(ListNode *L) { ListNode *p=L,*q; if (L->next->data==X)
{ printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”); return; }
for (;p->next->data!=X; q=p; p=p->next); // 删除指针p所指向的结点 q->next=p->next; delete p; }
4．void countnode(bitree *bt,int &count)
{
if(bt!=0)
{count++; countnode(bt->lchild,count); countnode(bt->rchild,count);} }
五、填空题(11小题,共22分) 1． 栈是否满 栈是否空 2．(sq.rear+1)%(M+1)==sq.front； 3．(a)，((((b),c)),(d))
4．n，n-1
5．2i-1，(n+1)/2，(n-1)/2 6．插入类排序
【解答】O(nlog2n)，O(n2) 7．
8．n(n-1)/2 9．60
10．多对多
11．数据的逻辑结构在计算机中的表示
长沙理工大学 2014-2015学年一学期数据结构期末考试试卷7
