洛雅德科技学院
200 ~200 学年第
学期期末试题——数据结构(C语言)
三 四 五 六 总分 题号 分数 一 二 本课程为闭卷考试，试卷共六道大题，试卷满分100分，考试时间120分钟。
一．选择题（10×2分）：共10小题，请将答案填入题中的括号中，每小题只有一个正确答案，错选或不选均不给分。
1．如果树的结点有4个兄弟，而且B为A的双亲，则B的度为（ ）
Ａ．3 Ｂ．4 C．5 D．1
2．设有一个栈，元素的进栈次序为A,B,C,D,E，则下列（ ）是不可能的出栈序列。 A．A,B,C,D,E B．B,C,D,E,A C．E,A,B,C,D D．E,D,C,B,A
3．在所有排序方法中，关键字的比较次数与记录的初始排列无关的是（ ）。 A．快速排序 B．冒泡排序
C．直接插入排序 D．简单选择排序
4．设一棵二叉树共有20个度为2的结点，则叶子结点共有（ ）个。
A．40 B．19 C．20 D．21 5．在具有N个单元的顺序存储循环队列中，假定front和rear分别为对头指针和对尾指针，则判断对满的条件为（ ）。
A．front== rear B．(rear+1)%MAXSIZE==front C．front-rear==1 D．rear%MAXSIZE==front 6．设有1000个元素，用二分法查找时，最小比较次数为（ ）
Ａ．0 Ｂ．1 C．10 D．500 7．一个元素进入队列的时间复杂度是（ ）。 A．O(1) B．O(n) C．O(n2) D．O(log2n)
8．一棵完全二叉树中根结点的编号为1，而且23号结点有左孩子但没有右孩子，则完全二叉树共有（ ）个结点。
A．24 B．45 C．46 D．47
9．如某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，数据元素间的关系为R={,,
A．线性结构 B．树结构 C．链表结构 D．队列结构
10．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（ ）个元素。
1
A．n-i B．n-i+1 C．n-i-1 D．i 二．填空题（20分）：每空2分，
１．后序序列和中序序列相同的二叉树为 、后序序列和前序序列相同的二叉树为 。
2．已知某算法的执行时间为n+n2,n代表问题规模，则该算法的时间复杂度是 。
3．数据结构有线性结构、树结构、 、 等几种逻辑结构。
4．采用快速排序法进行排序时，如果 时，排序效率会大大降低。 5．在一个长度为n的顺序表中插入一个元素，最少需要移动 元素，最多需要移动 元素，
6．如果指针p指向一棵二叉树的一个结点，则判断p没有左孩子的逻辑表达式为 。
7．栈的原则是 。 三．简答题（4×5分）
1． 写出线性表(26,45,12,20,30)采用快速排序算法排序后，第一趟排序过程及结果。（5分）
2． 线性表采用插入排序算法排序几趟后，有序部分是(16,20,40)，无序部分是(18,25)，则
下一趟的排序需要移动几个元素？写出下一趟结束的结果。（5分）
3． 给出下图所示的二叉树的中序遍历结果。（5分）
A B C D E F G
4． 试说明单链表采用头结点的优点。（5分）
四．判断题（5×2分）
１．如果某数据结构的每一个元素最多只有一个直接前驱，则其必为线性表。( ) 2．快速排序算法在最好的情况下时间复杂度是O(n)。( ) 3．进栈、出栈操作的时间复杂度是O(n)。( ) 4．进栈操作时，必须判断栈是否已满。( )
5．一个单链表不能采用折半查找法进行查找。( )
2
五．程序填空题（3×5分）
1．已知QUEUE表示循环队列的数据结构，函数leavequeue是将对头元素的值放入变量e，然后删除对头元素，操作成功返回1，否则返回0。完成以下程序。（4分） typedef struct {
int data[100]; int front; int rear; } QUEUE;
leavequeue (QUEUE *Q, int *e) {
if( ) { return 0; }
*e = Q->data[Q->front];
Q-front = ; return 1; }
2．以下函数ins的功能是在顺序表a中找到第一个值为x的元素，然后在该元素之前插入一个值为y的元素，如果找不到值为x的元素，则新元素成为顺序表的最后一个元素。插入成功返回1，否则返回0。完成以下程序。(8分)
typedef srruct { int data[100]; int len; } SQ;
int ins(SQ *a, int x, int y) { int k,j;
if( ) return 0; for(k=0;klen;++k) { if(a->elem[k] == x) { break;
}
}
if(k == a->len) { --k;
} else {
for (i=a->len-1;i>k;--i) {
; } }
3
=y; a->len ; return 1;
}
3．已知一个单链表的表头指针为h，每个结点含元素值data和下一个结点的地址next。链表一共有5个结点，其元素值分别为100,200,300,400,500，经过下列语句后，输出什么结果？。（3分）
for (p=h;p->data<300;p=p->next) { p->next = p->next->next;
}
printf(“%d”,p->data);
六．算法设计题（15分）
1．设计冒泡排序的算法。数据类型定义如下：（8分） #define MAXSIZE 100 typedef int KeyType; typedef struct node {
KeyType key;
infotype otherinfo;
} ElemType; typedef struct {
ElemType elem[MAXSIZE]; int length;
} S_TBL;
4
2．编写算法查找不带头结点的单链表中的第i个结点，如找到返回1，否则返回0。（7分） 已知单链表结点数据结构如下：
typedef struct node
{
int data;
struct node *next;
} LNode, *LinkList; 答案及评分标准：
数据结构(C语言)答案及评分标准
一．选择题（10×2分）：每小题只有一个正确答案，错选或不选均不给分。 1 C
二．填空题（20分）：每空2分。
1．没有右子树的二叉树 只有根的二叉树; 2．O(n2); 3．图结构 集合; 4．降序排列; 5．0，n; 6．P->lchild==NULL； 7．先进后出。
三．简答题（4×5分）
1．20 12 26 45 30。
2．需移动两个元素，16 18 20 40。 3．DBAFGEC
4．解决单链表的“第一个结点问题”，使头指针变量不为空。
四．判断题（5×2分）
1．×；2．√；3．×；4．×；5．√
五．程序填空题（3×5分）
1．Q->front == Q->rear;(Q->front+1)0; 2．a->len>=100;a->elem[i]=a->elem[i-1];a[k];++; 3．300
2 C 3 D 4 D 5 B 6 B 7 A 8 C 9 B 10 A 5
六．算法设计题（15分） 1．void bublesort(ElemType *r)
{
int i = 0; int j = 0;
ElemType temp;
for (i=0; i for (j=n-2; j>=I;--j) { if (r[j+1].key < r[j].key) { temp = r[j+1]; r[j+1] = r[j]; r[j] = temp; } } } } 2．LNode *Get_LinkList(inkList L, int i) { LNode *p = L; int j = 0; while(p->next != NULL && j < i) { p = p->next; ++j; } if (j == i) { return p; } else { return NULL; } } 6