数据结构与算法
一、选择题(每题2分，共52分)
1.计算机内部数据处理的基本单位是_________。
A 数据 B 数据元素 C 数据项 D 数据库
2.数据在计算机内有链式和顺序两种存储方式，在算法时间的执行效率上，链式存储比顺序存储要_______。
A 高 B 低 C 相同 D 不好说 3.下面关于线性表的叙述中，错误的是哪一个____________？
A 线性表中任何一个元素有且仅有一个直接前趋、有且仅有一个直接后继。 B 线性表采用顺序存储，不便于进行插入和删除操作。 C 线性表采用链式存储，不必占用一片连续的存储单元。 D 线性表是一个有限序列，可以为空。
4.在一个长度为n的顺序表中第i个元素（0<=i<=n-1）之前删除一个元素时，需向前移动________个元素。
A n-i B n-i+1 C n-i-1 D i
5.设单链表中指针p指向结点m，若要删除m之后的结点(若存在)，则需要修改 针操作为_________。
A p=p->next; B p->next=p->next->next; C p->next=p; D p=p->next->next;
6.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行_______。
A s->next=p->next; p->next=s; B q->next=s;s->next=p; C p->next=s->next;s->next=p; D p->next=s;s->next=q; 7.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是_______。 A edcba B decba C dceab D abcde 8.一个栈的输入序列为1,2,3?100，若输出序列的第1个元素是100，输出第51个元素是_________。
A 51 B 超出范围 C 50 D 49 9.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行_________。 A hs->next=s; B s->next=hs;hs=s; C s->next=hs->next;hs->next=s; D s->next=hs;hs=hs->next; 10.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为__________。
第 1 页 共 5 页
A (rear-front+m)%m B rear-front+1 C (front-rear+m)%m D (rear-front)%m
11.在一个链队列Q中，假定front和rear分别为队首和队尾指针，且队头的后继元素存在，则删除一个元素的操作为_______。 A Q->front=p;p=Q->front->next;free(p);
B p=Q->front->next;Q->front=Q->front->next;free(p); C p=Q->front;Q->front=p->next;free(p); D Q->front->next=Q->front;p=Q->front;free(p); 12.表达式a*(b+c)-d的前缀表达式是_______。
A *+-abcd B -*a+bcd C abc+*d- D -+*abcd 13.若串S=′Chinese′,其子串的数目是_______。
A 7 B 28 C 29 D 8 14.下面关于串的的叙述中，哪一个是不正确的__________？ A 串是字符的有限序列 B 空格串是由1个空格构成的串 C 串的长度是指串中所含字符的个数
D 求子串q在主串p中首次出现的位置的算法称为匹配
15.已知二维数组A[8][10]中，元素A[2][0]的地址为560，每个元素占4个字节，则元素A[1][0]的地址为_______。
A 520 B 522 C 524 D 518
16.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为_______个。 A 4 B 5 C 6 D 7
17.一棵具有16个结点的完全二叉树，对其结点编号(根结点为0)，则对编号为7的结点x，它的双亲结点及右孩子结点的编号分别为________。 A 2,16 B 2,15 C 3，16 D 3,15 18.按照二叉树的定义，具有三个结点的二叉树有_________种。 A 3 B 4 C 5 D 6
19.设给定权值总数有n 个，其哈夫曼树的结点总数为________。 A 不确定 B 2n C 2n+1 D 2n-1
20. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为_______。 A 1 B 2 C 3 D 4
21.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树_______。 A 是完全二叉树 B 不是完全二叉树 C 是满二叉树 D 不是满二叉树
第 2 页 共 5 页
22.无向图中一个顶点的度是指图中_________。
…… 此处隐藏1103字 ……
4.写出下图中二叉树先序遍、中序遍历和后序遍历的序列。(2分)
5.已知一组关键字为{25,23,36,72,79,82,48,40,16,35}，请描述出对其进行两归并排序的过程。(5分)
第 5 页 共 5 页