数据结构试卷1(含答案)

数据结构试卷

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列选项中与数据存储结构无关的术语是（）

A.顺序表

B.链表

C.链队列

D.栈

2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（）

A.n-1

B.n

C.2n-1

D.2n

3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（）

A.rear=(rear-1)%m;

B.front=(front+1)%m;

C.front=(front-1)%m;

D.rear=(rear+1)%m;

4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（）

A.堆栈

B.多维数组

C.队列

D.线性表

5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）

A.求子串

B.串联接

C.串匹配

D.求串长

6.对于广义表A，若head(A)等于tail(A)，则表A为（）

A.( )

B.(( ))

C.(( ),( ))

D.(( ),( ),( ))

7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（）

A.结点均无左孩子的二叉树

B.结点均无右孩子的二叉树

C.高度为n的二叉树

D.存在度为2的结点的二叉树

8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（）

A.4

B.5

C.7

D.8

9. 某算法有3个程序段，第一程序段的执行次数为错误！未找到引用源。，第二个程序段执行次数为4n，第三个程序段的执行次数为0.06错误！未找到引用源。，则该算法的时间复杂度为（）。

A．O（n） B．O（错误！未找到引用源。） C．O（错误！未找到引用源。） D．O （错误！未找到引用源。）

10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={，，，，}，图G的拓扑序列是（）

A.V1,V2,V3,V4

B.V1,V3,V2,V4

C.V1,V3,V4,V2

D.V1,V2,V4,V3

11.平均时间复杂度为O(n log n)的稳定排序算法是（）

A.快速排序

B.堆排序

C.归并排序

D.冒泡排序

12.已知关键字序列为(51，22，83，46，75，18，68，30)，对其进行快速排序，第一趟划分完成后的关键字序列是（）

A.(18,22,30,46,51,68,75,83)

B.(30,18,22,46,51,75,83,68)

C.(46,30,22,18,51,75,68,83)

D.(30,22,18,46,51,75,68,83)

13.某索引顺序表共有元素395个，平均分成5块。若先对索引表采用顺序查找，再对块中元素进行顺序查找，则在等概率情况下，分块查找成功的平均查找长度是（）

A.43

B.79

C.198

D.200

14.在含有10个关键字的3阶B-树中进行查找，至多访问的结点个数为（）

A.2

B.3

C.4

D.5

15.设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B 中。对下三角矩阵中任一元素aij(设矩阵A是一个对称矩阵，为了节省空间，将其下三角部分按行优先存放在一维数组B中，对下三角矩阵中任一元素aij(i>=j)，在一维数组B中下标K的值是( )。

A、i(i-1)/2+j-1

B、i(i-1)/2+j

C、i(i+1)/2+j-1

D、i(i+1)/2+j

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16.数据结构由数据的逻辑结构、存储结构和数据的____________三部分组成。

17.在单链表中某结点后插入一个新结点，需要修改_______________个结点指针域的值。

18.设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、

c、f、e、a，则栈S的容量至少是________________。

19.长度为零的串称为________________。

20.广义表G=(a,b，(c，d，(e，f))，G)的长度为________________。

21.一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是________________。

22.一个有n个顶点的无向连通图，最少有________________条边。

23.当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法

中，运行效率最高的是________________。

24.设目标串T=“abccdcdccbaa”,模式P=“cdcc”则第___________次匹配成功。若字符串的长度为n,则子串的个数为___________

25.在归并排序中，若待排序记录的个数为20，则共需要进行____________趟归并

三、解答题（本大题共4小题，每小题5分，共20分）

26.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，

请回答下列问题：

(1)画出此二叉排序树；

(2)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林。

27.已知有向图的邻接表如图所示，请回答下面问题：

(1)给出该图的邻接矩阵；

(2)从结点A出发，写出该图的深度优先遍历序列。

28. 在一个算法中需要建立多个堆栈是可以选用下列两种种方案之一，试问：这三种方

案之间相比较各有什么优缺点？

（1） 分别用多个顺序存储空间建立多个独立的堆栈； （2） 多个堆栈共享一个顺序存储空间；

29. 设G=（V ,E ）以邻接表存储，如图所示，试画出图的深度优先和广度优先生成图。

四、算法阅读题（本大题共4小题，每小题5分，共20分） 30.阅读下列程序。

void f30(int A[]， int n) {

int i,j,m; for (i=1；i

for (j=0；j

m=A[i*n+j]； A[i*n+j]=A[j*n+i]； A[j*n+i]=m ； }

}

回答下列问题：

(1)已知矩阵B=???

?

? ??9 8 7 6 5 4 3 2 1 ，将其按行优先存于一维数组A 中，给出执行函数调

用f30(A ，3)后矩阵B 的值；

31.假设以二叉链表表示二叉树，其类型定义如下： typedef struct node { char data;

struct node*Ichild, *rchild; ∥左右孩子指针 } *BinTree ；

阅读下列程序。

void f31(BinTree T)

{

InitStack(S); ∥初始化一个堆栈S

while (T ||!StackEmpty(S)

{

while (T)

{

Push(S,T); T=T->lchild;

}

if (!StackEmpty(S))

{

T=Pop(S); printf(“%c”,T->data); T=T->rchild;

}

}

}

回答下列问题：

(1)已知以T为根指针的二叉树如图所示，

请写出执行f31(T)的输出结果：

(2)简述算法f31的功能。

32.阅读下列程序。

void f32(int A[],int n)

{

int i,j,m=l,t；

for (i=0; i

{

for (j=0；j

printf(“%d ”,A[j])；

printf(“＼n”);

m=0：

for (j=1; j

if (A[j-1]>A[j])

{

t=A[j-l];

A[j-1]=A[j]；

A[j]=t；

m=1；

}

}

}

回答问题：

已知整型数组A[ ]={34,26,15,89,42}，写出执行函数调用f32(A,5)后的输出结果。

33. 程序填空

（1）

//////直接插入排序

void InsertSort(int a[],int n)

{

int i,j,k=1;

for(i=2;i<=n;i++)

{ if(a[i]

{

a[0]=a[i];

_________;

for(j=i-2;a[0]

a[j+1]=a[j];

a[j+1]=a[0];}

printf("\n第%d趟结果为:",i-1);

for(k=1;____;k++)

printf(" %d",a[k]);

}

}

五、算法设计题（本题10分）

34.假设用带头结点的单循环链表表示线性表，单链表的类型定义如下：

typedef struct node {

int data;

struct node*next;

}LinkNode，*LinkList;

编写程序，求头指针为head的单循环链表中data域值为正整数的结点个数占结点总数的比例，若为空表输出0，并给出所写算法的时间复杂度。函数原型为：float f34(LinkList head):

一、单项选择题

1—5 D B D A A 6—10 B C B C A 11—15 C D A B D

二、填空题

16、运算

17、 2

18、 3

19、空串

20、 4

21、左右指针域均为空

22、 n1

23、直接插入排序

24、 6 n(n+1)/2

25、 5

三、解答题

26、（1）

（2）

27、该图的邻接矩阵如下：

0 1 1 0 0

0 0 1 1 0

0 0 0 0 1

0 0 1 0 0

1 0 0 1 0

(2)图的深度优先遍历序列如下：

A B C E D

28、（1）每个栈仅用一个顺序存储空间时，操作简便，但分配存储空间小了，容易产生

溢出，分配空间大了，容易造成浪费，各栈不能共享空间。

（2）多个栈共享一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才能产生溢出，其缺点是当一个栈满时要向左、右栈查询有无空闲单元。如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时，查询空闲单元、移动元素和修改栈底栈顶指针的操作频繁，计算复杂并且耗费时间。

29、设从顶点1开始遍历，则深度优先生成树为

1---2---3---4---5

宽度优先生成树为

1

2 3 4

5

输出结果：V1 V4 V3 V6 V2 V5

四、算法阅读题

30、矩阵B 的值为：

1 4 7

2 5 8

3 6 9

31、（1）执行f31(T)的输出结果为：

C B E

D F A G H

(2)算法f31 实现的功能是：利用栈实现二叉树的中序遍历。

32、执行函数调用f32(A,5)后的输出结果是：

34,26,15,89,42

26,15,34,42,89

15,26, 34,42,89

33、a[i]=a[i-1] k<=

五、算法设计题

34、解：

float f34(LinkList head)

｛

LinkList p?

Int count=0, scount=0? //count 代表data 域值为正整数的结点个数，scount 代表总结点个数。

If(head>

next==head) return 0?

Else

{

P=head?

Do

{ p=p>

next?

Scount++?

If(p>

data>0)?

}

While(p>

next!=head)?

}

Printf(“正整数的结点个数占结点总数的比例是:%d”,count/scount*1.0)?｝

此算法的时间复杂度为：o(n)

数据结构模拟试题1

一、填空题（共20分，每空1分）。 1.数据结构是研究数据元素之间抽象化的相互关系和这种关系在计算机中的存储结构表 示，通常有下列四种存储结构：（1）、（2）、（3）和（4）。 2.评价算法的标准很多，通常是以执行算法所需要的（5）和所占用的（6）来判别一 个算法的优劣。 3.队列操作的原则是（7），栈的插入和删除操作在（8）进行。 4.对循环队列Q，它的最大存储空间是MAXSIZE，队头指针是front，队尾指针是rear， 采用少用一个存储单元的方法解决假溢出时，队满的判断条件是（9），队空的判断条件是（10）。 5.在以head 为表头指针的带有头结点的单链表和循环单链表中，判断链表为空的条件分 别为（11）和（12）。 6.假设二维数组A[6][8]，每个元素用相邻的4个字节存储，存储器按字节编址，已知 A[0][0]的存储位置为100，按行优先顺序存储的元素A[2][5]的第一个字节的地址为（13）。 7.空格串的长度为串中所包含（14）字符的个数，空串的长度为（15）。 8.有向图G 用邻接矩阵A[n][n] 存储表示，其第i 行的所有元素之和等于顶点i 的 （16）。 9.在关键字序列(12 ，23 ，34 ，45 ，56 ，67 ，78 ，89 ，91) 中折半查找 关键字为89和25的结点时，所需进行的比较次数分别为（17）和（18）。 10.请说出两种处理哈希冲突的方法（19）、_（20）_。 二、选择题（共20分，每题2分）。 1.对线性表，在下列哪种情况下应采用链式存储结构？（） A.经常需要随机存取元素 B.经常需要进行插入和删除操作 C.表中元素的个数不变 D.表中元素需要占据一片连续的存储空间 2.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功情况下，则平均比 较（）个结点。 A.n B.n/2 C.(n-1)/2 D.(n+1)/2 3.若对某线性表最常进行的操作是在最后一个元素之后插入和删除第一个元素，则采用 （）存储方式最节省运算时间。 A.单链表 B.双链表 C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表 4.在一个单链表中，若要删除p指针所指结点的后继结点，则执行（）。 A.p=p->next; p->next=p->next->next; B.p->next=p->next->next; C.p=p->next; D.p=p->next->next;

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素

数据库概论 习题参考答案

第1章绪论习题参考答案 1、试述数据、数据库、数据库管理系统、数据库系统的概念。（参见P3、4、5页） 参考答案： 描述事物的符号记录称为数据；数据库是长期储存在计算机内的、有组织的、可共享的数据集合；数据库管理系统是位于用户与操作系统之间的一层数据管理软件; 数据库系统是指在计算机系统中引入数据库后的系统，一般由数据库、数据库管理系统(及其开发工具)、应用系统、数据库管理员和用户构成。 2．使用数据库系统有什么好处?（参见P12页） 参考答案： 数据库系统使信息系统从以加工数据的程序为中心转向围绕共享的数据库为中心的阶段，这样既便于数据的集中管理，又有利于应用程序的研制和维护，提高了数据的利用率和相容性，提高了决策的可靠性。 3．试述文件系统与数据库系统的区别和联系。（8、9、10页） 参考答案： 1）数据结构化是数据库与文件系统的根本区别。 在文件系统中，相互独立的文件的记录内部是有结构的，管其记录内部已有了某些结构，但记录之间没有联系。数据库系统实现整体数据的结构化，是数据库的主要特征之一。 2）在文件系统中，数据的最小存取单位是记录，粒度不能细到数据项。而在数据库系统中，存取数据的方式也很灵活，可以存取数据库中的某一个数据项、一组数据项一个记录或或一组记录。 3）文件系统中的文件是为某一特定应用服务的，文件的逻辑结构对该应用程序来说是优化的，因此要想对现有的数据再增加一些新的应用会很困难，系统不容易扩充。而在数据库系统中数据不再针对某一应用，而是面向全组织，具有整体的结构化。5．试述数据库系统的特点。（9、10、11页） 参考答案： 数据结构化；数据的共享性高、冗余度低、易扩充；数据独立性高；数据由DBMS统一管理和控制。 6．数据库管理系统的主要功能有哪些? （4页）

计算机专业基础综合(数据结构)模拟试卷1

计算机专业基础综合（数据结构）模拟试卷1 (总分：72.00，做题时间：90分钟) 一、单项选择题(总题数：21，分数：42.00) 1.单项选择题1-40小题。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。（分数： 2.00）__________________________________________________________________________________________ 解析： 2.若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。 （分数：2.00） A.单链表 B.带有头指针的单循环链表 C.双链表 D.带有尾指针的单循环链表√ 解析：解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。 3.已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s的升序链表，则最坏情况下的时间复杂度是( )。 （分数：2.00） A.O(l) B.O(ls) C.O(min(l，s)) D.O(max(l，s)) √ 解析：解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。 4.线性表中存放的主要是( )。 （分数：2.00） A.整型常量 B.字符 C.数据元素√ D.信息元素 解析：解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。 5.下面的叙述中正确的是( )。 I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比 （分数：2.00） A.仅I √ B.仅Ⅱ C.仅Ⅲ D.I、Ⅱ、Ⅲ 解析：解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。而在顺序存储结构中查找第i个元素的时间与i的位置无关。 6.对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。 （分数：2.00） A.顺序表√

数据结构模拟试题1

一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1

C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

大工数据结构课程考试模拟试卷a

少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 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、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4

《数据结构》模拟试卷一及答案

模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( )

数据结构与算法 模拟试卷三四及参考答案

模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的

数据结构模拟试题一及答案汇编

学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2

数据结构模拟卷(含答案)经典习题培训讲学

数据结构模拟卷(含答案)经典习题

练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4

6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )

数据结构模拟题1

模拟题 一．单项选择题 1. 如图所示的4棵二叉树中，哪一个是平衡二叉树 A. B. C. D. 2. 若一个算法的语句频度之和为T(n)=3n+ nlog2n + n2,则算法的时间复杂度为。 A. nlog2n + n2 D.nlog2n 3. 插入和删除操作只能在同一端进行的线性表，成为。 A.队列 B.循环队列 C.栈 D.循环栈 4. 一棵树Tr转换成相应的二叉树Bt，那么对Tr的后序遍历是对Bt的。 A．先序遍历B．中序遍历C．后序遍历D．无法确定 5. 判定一个循环队列Q（最多元素为m0）为空的条件是。 A．= =Q. Rear B. = =( + 1 ) % m0 C．!= D. != ( Q . rear +1 ) % m0 6. 广义表(（a,b,( ),c),(d,(e))，（）)的长度是。 .4 C 7. 在一个无向图中，所有顶点的度数之和，是其所有边数之和的倍。 A．1/2 B．1 C．2 D．4 8. tail（head（（a，b），c，（c，d）））的结果是。 A．b B．（b）C．（a，b）D．（c，d） 9. 深度为k的满二叉树有个分支 ．．结点。 -2 C +1 10.一棵有n个结点的树，在把它转换成对应的二叉树之后，该二叉树根结点的左子树上共有个结点。 A．n-2 B．n-1 C．n+1 D．n+2 11. n个顶点的带权无向连通图的最小生成树包含条边。 2 +1 12. 如图，若从顶点a出发按广度优先法进行遍历，可能得到的一种顶点序列是。 A．abcedf B．abcefd C．aebcfd D．acfdeb 13. 无向图的邻接矩阵是矩阵。 A.对称 B.上三角 C.下三角 D.稀疏 14.一个无向连通网图的最小生成树。 A．可能不存在B．只有一棵C．一定有多棵D．有一棵或多棵 15. 在下面给出的各种排序算法中，只有是稳定排序算法。 A．堆排序B．快速排序C．直接选择排序D．冒泡排序

数据库的体系结构

数据库基础 （ 视频讲解：25分钟） 本章主要介绍数据库的相关概念，包括数据库系统的简介、数据库的体系结构、数据模型、常见关系数据库。通过本章的学习，读者应该掌握数据库系统、数据模型、数据库三级模式结构以及数据库规范化等概念，掌握常见的关系数据库。 通过阅读本章，您可以： 了解数据库技术的发展 掌握数据库系统的组成 掌握数据库的体系结构 熟悉数据模型 掌握常见的关系数据库 1 第 章

1.1 数据库系统简介 视频讲解：光盘\TM\lx\1\数据库系统简介.exe 数据库系统（DataBase System，DBS）是由数据库及其管理软件组成的系统，人们常把与数据库有关的硬件和软件系统称为数据库系统。 1.1.1 数据库技术的发展 数据库技术是应数据管理任务的需求而产生的，随着计算机技术的发展，对数据管理技术也不断地提出更高的要求，其先后经历了人工管理、文件系统、数据库系统等3个阶段，这3个阶段的特点分别如下所述。 （1）人工管理阶段 20世纪50年代中期以前，计算机主要用于科学计算。当时硬件和软件设备都很落后，数据基本依赖于人工管理，人工管理数据具有如下特点： ?数据不保存。 ?使用应用程序管理数据。 ?数据不共享。 ?数据不具有独立性。 （2）文件系统阶段 20世纪50年代后期到60年代中期，硬件和软件技术都有了进一步发展，出现了磁盘等存储设备和专门的数据管理软件即文件系统，文件系统具有如下特点： ?数据可以长期保存。 ?由文件系统管理数据。 ?共享性差，数据冗余大。 ?数据独立性差。 （3）数据库系统阶段 20世纪60年代后期以来，计算机应用于管理系统，而且规模越来越大，应用越来越广泛，数据量急剧增长，对共享功能的要求越来越强烈。这样使用文件系统管理数据已经不能满足要求，于是为了解决一系列问题，出现了数据库系统来统一管理数据。数据库系统满足了多用户、多应用共享数据的需求，它比文件系统具有明显的优点，标志着管理技术的飞跃。 1.1.2 数据库系统的组成 数据库系统是采用数据库技术的计算机系统，是由数据库（数据）、数据库管理系统（软件）、数

数据结构模拟试卷(含答案)

数据结构设计课程代码：7399 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆

数据结构模拟试题9

一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。

试述数据模型的概念

试述数据模型的概念，数据模型的作用和数据模型的三个要素: 答案： 模型是对现实世界的抽象。在数据库技术中，表示实体类型及实体类型间联系的模型称为“数据模型”。 数据模型是数据库管理的教学形式框架，是用来描述一组数据的概念和定义，包括三个方面： 1、概念数据模型（Conceptual Data Model）：这是面向数据库用户的实现世界的数据模型，主要用来描述世界的概念化结构，它使数据库的设计人员在设计的初始阶段，摆脱计算机系统及DBMS的具体技术问题，集中精力分析数据以及数据之间的联系等，与具体的DBMS 无关。概念数据模型必须换成逻辑数据模型，才能在DBMS中实现。 2、逻辑数据模型（Logixal Data Model）:这是用户从数据库所看到的数据模型，是具体的DBMS所支持的数据模型，如网状数据模型、层次数据模型等等。此模型既要面向拥护，又要面向系统。 3、物理数据模型（Physical Data Model）:这是描述数据在储存介质上的组织结构的数据模型，它不但与具体的DBMS有关，而且还与操作系统和硬件有关。每一种逻辑数据模型在实现时都有起对应的物理数据模型。DBMS为了保证其独立性与可移植性，大部分物理数据模型的实现工作又系统自动完成，而设计者只设计索引、聚集等特殊结构。 数据模型的三要素： 一般而言，数据模型是严格定义的一组概念的集合，这些概念精确地描述了系统的静态特征（数据结构）、动态特征（数据操作）和完整性约束条件，这就是数据模型的三要素。 1。数据结构 数据结构是所研究的对象类型的集合。这些对象是数据库的组成成分，数据结构指对象和对象间联系的表达和实现，是对系统静态特征的描述，包括两个方面： （1）数据本身：类型、内容、性质。例如关系模型中的域、属性、关系等。 （2）数据之间的联系：数据之间是如何相互关联的，例如关系模型中的主码、外码联系等。 2 。数据操作 对数据库中对象的实例允许执行的操作集合，主要指检索和更新（插入、删除、修改）两类操作。数据模型必须定义这些操作的确切含义、操作符号、操作规则（如优先级）以及实现操作的语言。数据操作是对系统动态特性的描述。 3 。数据完整性约束 数据完整性约束是一组完整性规则的集合，规定数据库状态及状态变化所应满足的条件，以保证数据的正确性、有效性和相容性。

数据结构与算法模拟试卷一、二及参考答案

四川大学 《数据结构与算法分析》课程 考试模拟试卷 模拟试卷一 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩 子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双 亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};