第二单元
⒈设线性表存放在向量A[arrsize]的前num个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。
int insert(int A[arrsize],int num,int x)
{
if (num==arrsize) return(-1);
i=num-1;
while(i>=0&&A[i]>x)
{
A[i+1]=A[i];
i--;
}
A[i+1]=x;
num++;
return(1);
}
⒉已知一顺序表A，其元素值非递减有序排列，编写一个算法删除顺序表中多余的值相同的元素。
typedef struct{
datatype data[maxsize];
int last;
}seqlist;
void delete(seeqlist *A)
{
i=0;
while (ilast)
{
k=i+1;
while (k<=A->last&&A->data[i]==A->data[k])
k++;
n=k-i-1;
for (j=k;j<=A->last;j++)
A->data[j-n]=A->data[j];
A->last=A->last-n;
i++;
}
}
⒊写一个算法，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。
typedef struct{
datatype data[maxsize];
int last;
}seqlist;
void delete(seeqlist *A,int x,int y)
{
j=0;
for (i=0;i<=A->last;i++)
if (A->data[i]>x&&A->data[i]
j++;
else
{
A[i-j]=A[i];
A->last= A->last-j;
.
. 数据结构的基本概念
选择题
（1） 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。
A．线性结构 B．非线性结构 C．存储位置 D．指针
（2） 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应该是（ ）。
A．树 B．图 C．线性表 D．集合
（3） 计算机所处理的数据一般具有某种内在联系，这是指（ ）。
A．数据和数据之间存在某种关系 B．元素和元素之间存在某种关系
C．元素内部具有某种结构 D．数据项和数据项之间存在某种关系
（4） 在数据结构中，与所使用的计算机无关的是数据的（ ）。
A．树 B．图 C．线性表 D．集合
（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（ ）。
A．数据的处理方法 B．数据元素的类型
C．数据元素之间的关系 D．数据的存储方法
（6） 在链接存储结构中，要求（ ）。
A．每个结点占用一片连续的存储区域 B．所有结点占用一片连续的存储区域
C．结点的最后一个域是指针类型 D．每个结点有多少个后继就设多少个指针
（7） 下列说法不正确的是（ ）。
A．数据元素是数据的基本单位 B．数据项是数据中不可分割的最小单位
C．数据可由若干个数据项构成 D．数据元素可由若干个数据项构成
（8） 以下与数据的存储结构无关的术语是（ ）。
A．循环队列 B．链表 C．散列表 D．栈
（9） 以下术语属于逻辑结构的是（ ）。
A．顺序表 B．哈希表 C．有序表 D．单链表
（10） 可以用（ ）定义一个完整的数据结构。
A．数据元素 B．数据对象 C．数据关系 D．抽象数据类型
数据结构复习题（附答案）
1. 快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log
2n) B．O(nlog
2
n) C．O (n) D. O (n2)
2．设⼀棵⼆叉树的深度为k，则该⼆叉树中最多有（ D ）个结点。
A. 2k-1
B. 2k
C.2k-1
D. 2k-1
3．⼆叉树中第i(i≥1)层上的结点数最多有（ C ）个。
A. 2i
B. 2i
C. 2i-1
D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。
A. p->next=p->next->next
B. p=p->next
C. p=p->next->next
D. p->next=p
5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，⼀个元素出栈后即进⼊队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量⾄少应该是（ C ）。A. 6
B. 4
C. 3
D. 2
6.设有以下四种排序⽅法，则（ B ）的空间复杂度最⼤。
A. 冒泡排序
B. 快速排
C. 堆排序
D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。
A. 3
B. 4
C. 5
D. 18．根据⼆叉树的定义可知⼆叉树共有（ B ）种不同的形态。
A. 4
B. 5
C. 6
D. 7
9．对⼀个算法的评价，不包括如下（ A ）⽅⾯的内容。
A．并⾏性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在⼆叉排序树中插⼊⼀个结点的时间复杂度为（ C ）。
A．O(1) B．O(n) C．O(log
2
n) D．O(n2)
11. 队列是⼀种（ B ）的线性表。
A．先进后出B．先进先出 C．只能插⼊D．只能删除12．采⽤开放定址法处理散列表的冲突时，其平均查找长度（ C ）。
A．低于链接法处理冲突 B. 与链接法处理冲突相同
C．⾼于链接法处理冲突 D．⾼于⼆分查找
- 1 - June
Jan July Feb Dec Nov
Oct Sep Aug May
Apr Mar 数据结构复习样题答案
一. 单项选择题
1. B 2. A 3. A 4. D 5. C 6. D 7. B 8. C
二. 填空题
9. 基本操作
10. 从表中任一结点出发均可找到表中其他结点
11. 栈
12. 队尾
13. 各结点均无左孩子
三. 解答题
17．后序线索; 后序遍历序列……省略
18.已知一个长度为12的表为
（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）
（1） 试将表中元素依次插入到一棵初始为空的二叉排序树（字符串之间按字典顺序比较大小）。画出该二叉排序树，并求出等概率情况下查找成功的平均查找长度。
（2） 设哈希表长度为13，哈希函数H（k）= i/2，其中i为关键字k中第一个字母在字母表中的序号（例如A和D的序号分别为1和4），用链地址法解决冲突。请画出通过依次插入表中元素所构造的散列表，并求出在等概率情况下查找成功的平均查找长度。
0 1 2 3 4 5 6 7 8 9 10 11 12
19.假设电文中仅由a到h共8个字母组成，字母在电文中出现的频度依次为 ECBDKAS
FJan
Feb Mar
Apr June May
July Aug Sep
Oct
Nov Dec
成功的平均查找长度＝42/12
成功的平均查找长度＝18/12 - 2 - 7，19，2，6，32，3，21，10
请画出由此构造的哈夫曼树（要求树中所有结点的左右孩子必须是左大右小），并写出这8个字母相应的哈夫曼编码。
字符 哈夫曼码
a 0101
b 11
c 01111
d 0110
e 00
f 01110
g 10
h 0100
20.若对序列（25，19，7，41，29，12，23，26）按升序排序，请分别给出
