长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(A卷)
班级:___________学号:___________姓名:___________得分:___________
题号 得分 阅卷 一 二 三 四 五 六 七 八 九 十 成绩 复核 题目部分，(卷面共有32题,100分,各大题标有题量和总分) 一、应用题(2小题,共16分)
1．将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。
2．一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 二、判断正误(5小题,共10分)
1．线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
2．如果两个串含有相同的字符，则说明它们相等。 3．哈夫曼树中没有度数为1的结点。（ ） 4．带权无向图的最小生成树是唯一的。（ ） 5．堆是完全二叉树，完全二叉树不一定是堆。（ ） 三、单项选择题(10小题,共20分)
1．表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，删除一个元素所需移动的平均个数为（ ）。
A、(n-1)/2 B、n C、n+1 D、 n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（ ）存储方式最节省运算时间。
A 单向链表 B 单向循环链表 C 双向链表 D 双向循环链表 3．在下列链表中不能从当前结点出发访问到其余各结点的是（ ）。
A．双向链表 B．单循环链表 C．单链表 D．双向循环链表
4．已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个
元素的地址是（ ）。
A 108 B 180 C 176 D 112
5． 设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（ ）。 A 5，3，4，6，1，2 B 3，2，5，6，4，1
C 3，1，2，5，4，6 D 1，5，4，6，2，3 6．以下论述正确的是（ ）。
A．空串与空格串是相同的 B．\是\的子串 C．空串是零个字符的串 D. 空串的长度等于1
7．将10*10的对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。 A 100 B 40 C 55 D 80
8．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（ ）个空指针域。
A 2m-1 B 2m C 2m+1 D 4m
9．对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ ）个， A．1 B．2 C．3 D．4
10．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（ ）。 A 1 B 2 C 3 D 4
四、算法设计题(4小题,共32分)
1．设计判断单链表中元素是否是递增的算法。 2．设计一个求结点x在二叉树中的双亲结点算法。
3．假设在长度大于 1 的循环链表中，即无头结点也无头指针， S 为指向链表中某个结点的指针，试编写算法删除结点 S 的前趋结点。
4．在链式存储结构上用递归方式建立一棵二叉排序树。
五、填空题(11小题,共22分)
1．由两个栈共享一个存储空间的好处是（ ）
2．循环队列的队首指针为front，队尾指针为rear，则队空的条件为（ ）。
3．设循环队列存放在向量sq.data[0:M]中，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。
4．当循环队列非空且队尾指针等于队头指针时，说明循环队列已满，不能进行入队运算。这种情况称为（ ）。
5．设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线
上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有（ ）个数据元素。
6．图的深度或广度优先搜索遍历时的空间复杂度均为_________ 7．N个顶点的连通图中边的条数至少为（ ）
8．设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有（ ）关系。 9．一个好的哈希函数其转换地址应尽可能 ，而且函数运算应尽可能 10．堆排序法属于（ ）
11．快速排序算法的空间复杂度平均情况下为（ ），最坏的情况下为（ ）。
长沙理工大学计算机与通信工程学院
2014-2015学年一学期数据结构期末考试试卷(A卷)
答案部分，(卷面共有32题,100.0分,各大题标有题量和总分) 一、应用题(2小题,共22分)
1．【解答】二叉排序树如图所示，其平均查找长度=1+2×2+3×2+4×2=19/7
2．
0 1 2 3 4 5 6 7 8 9 10 11 12 78 查找成功的平均查找长度：ASL SUCC=14/10= 1.4
二、判断正误(5小题,共10分) 1．错 2．错 3．对 4．错 5．对
三、单项选择题(10小题,共20分) 1． A 2． D 3．C 4． D 5．B 6．C 7．C 8．B 9．D 10．B
四、算法设计题(4小题,共32分)
1．int isriselk(lklist *head) {
if(head==0||head->next==0) return(1);else
q=p,p=p->next)if(q->data>p->data) return(0);
return(1); }
15 03 57 45 20 31 23 36 12 For(q=head,p=head->next; p!=0;
2．typedef struct node {datatype data; struct node *lchild,*rchild;} bitree; Bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x) {
if (bt!=0 && flag==0)
if (bt->data==x) { flag=1; return;} Else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x);
preorder(bt->rchild,x); }
}
void parent(bitree *bt,char x) {
int i;
preorder(bt,x);
for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break; if (flag==0) printf(\
else if (i<=r) printf(\}
3．void delete( LinkList s )
{ pre=s; q=pre-> next;
while (q -> next!=s) { pre=q;
q=q -> next; } pre -> next=s; free(q); }
4．#define n 10
typedef struct node{int key; struct node *lchild,*rchild;}bitree; void bstinsert(bitree *&bt,int key) {
if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;} else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key); }
void createbsttree(bitree *&bt) {
int i;
for(i=1;i<=n;i++) bstinsert(bt,random(100)); }
五、填空题(11小题,共22分)
1．节省存储空间，降低上溢发生的机率 2． front == rear
3．(sq.rear+1)%(M+1)==sq.front；
4．上溢
5． i(i+1)/2+j-1 6． 7．N-1 8．m=2e
9．均匀 简单 10．选择类排序
11．O(nlog2n)， O(n)
长沙理工大学 2014-2015学年一学期数据结构期末考试试卷5
