考研试题--数据结构

2006年

一、单项选择题

1、计算计算法必须具备输入、输出和（ ）5个特性。

A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 2、以下关于链式存储结构的叙述哪一条是错误的？（ ）

A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构 B.逻辑上相邻的结点物理上不必邻接

C.可以通过计算直接确定第i个结点的存储地址 D.插入、删除运算操作方便，不必移动结点 3、下面算法的时间复杂度为（ ） Int f(unsigned int n){ If(n==0||n==1) return 1; Else return n*f(n-1); }

A.O(1) B.O(n) C.O(n2) D.O(n!)

4、在包含1000个元素的线性表中实现如下各运算，哪一个所需的执行时间最长？ A.线性表按顺序方式存储，在线性表的第10个结点后面插入一个新结点 B.线性表按链接方式存储，在线性表的第10个结点后面插入一个新结点 C.线性表按顺序方式存储，删除线性表的第990个结点 D. 线性表按链接方式存储，删除指针P所指向的结点

5、在一个单链表HL（不带头结点）中，若要向表头插入一个由指针p指向的结点，则执

行（ ） A.HL=p;pnext=HL; B.pnext=HL; HL=p;

C.pnext=HL; p=HL; D.pnext=HLnext; HLnext=p;

6、循环队列用数组A[0…m-1]存放其元素值，已知其头尾指针分别为front和rear，则当前

元素个数为（ ） A.rear-front B.rear-front+1 C.rear-front-1 D.(rear-front+m) mod m E.以上答案都不对

7、以下哪一个不是栈的基本运算？（ ）

A.删除栈顶元素 B.删除栈底元素 C.判断栈是否为空 D.将栈置为空栈 8、以下关于广义表的叙述中，正确的是（ ） A.广义表是0个或多个单元素或子表组成的有限序列 B.广义表至少有一个元素是子表 C.广义表不可以是自身的子表 D.广义表不能为空表

9、设待排序关键码序列为（25，18，9，33，67，82，53，95，12，71），要按关键码值递

增的顺序进行排序，采取以第一个关键码为分解元素的快速排序法，第一趟完成后关键

码95被放到了第几个位置?( )

A.7 B.8 C.9 D.10

10、一棵含有102个结点的完全二叉树存储在数组A[1…102]中，对1≤k≤102，若A[k]

是叶子结点，则k得最小值是：（ ）

A.50 B.51 C.52 D.53

11、如果一棵二叉树中任一结点的值都大于其左子树中所有结点的值，且小于其右子树中

所有结点的值，现欲遍历得到各结点的序列为递增序列，应采用何种遍历方法？（ ） A.线序遍历 B.中序遍历 C.后序遍历 D.层次遍历 12、由3个结点可以构成多少棵不同形态的二叉树？（ ）

A.3 B.4 C.5 D.6

13、设森林F中有3棵树T1、T2、T3，其结点个数分别是n1,n2,n3，则与森林F对应的二

叉树根结点的右子树上的结点个数是（ ）

A.n1 B.n1+n2 C.n3 D.n2+n3

14、已知一个图如下图所示，在该图的最小生成树中各边上权值之和为（ ） A.31 B.36 C.38 D.43

15、在上图的最小生成树中，从顶点V1到顶点V6的路径为（ ）

A.V1,V3,V6 B.V1,V4,V6 C.V1,V5,V4,V6 D.V1,V4,V3,V6 二、填空题

1、设r指向单链表最后一个结点，要在最后一个结点之后插入s所指向的结点，需执行

的三条语句是____________、________________、______________。

2、设一个链栈的栈顶指针为ls，栈中结点格式为

_____________。若栈不空，则退栈操作的三条语句_____________、_______________、

________________。

3、树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和____________________. 4、一个有向图G中若有弧、和，则在图G的拓扑序列中，定点Vi，Vj和Vk的相对位置为______________________。 5、索引顺序表上的查找分两个阶段：（1）__________________，（2）______________。 6、在串S=“structure”中，以t为首字符的子串有__________个。 7、在下述算法中，标记（4）、（5）的两个语句的时间复杂度分别为：__________________、

_______________________。

For (i=1; i<=n;i++) (1) For(j=1;j<=n;j++) (2) { c[i][j]=0; (3) For(k=1;k<=n;k++) (4) c[i][j]=c[i][j]+a[i][k]*b[k][j]; (5)

}

8、栈顶的位置是随着_____________________操作而变化的。 三、判断正误并说明理由

1、查找表的逻辑结构是集合。

Info|link 栈空的条件是

2、在索引顺序文件中插入新的记录时，必须复制整个文件。

3、如果某种排序算法是不稳定的，则该方法没有实际的应用价值。

4、对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O（n2）。 5、双链表中至多只有一个结点的后继指针为空。 四、综合应用题。

1、将两个栈存入数组V[1…m]中应如何安排最好？这时栈空、栈满的条件是什么？ 2、有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表（用数组表

示）进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字不同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出数值为c，那么这个记录在新的有序表中的合适的存放位置即为c。

（1）给出适用于计数排序的数据表定义。 （2）编写实现计数排序的算法。

（3）对于有n个记录的表，比较次数是多少？

（4）与直接选择排序相比，这种方法是否更好？为什么？ 3、设二叉树BT的存储结构如下：

1 2 3 4 5 6 7 8 9 10 Left Data Right 0 J 0 0 H 0 2 F 0 3 D 9 7 B 4 5 A 0 8 C 0 0 E 0 10 G 0 1 I 0 请完成下列各题：

（1） 画出二叉树BT的逻辑结构。 （2） 二叉树BT的高度。

（3） 如果该二叉树是某可按孩子兄弟法转换而成的，请画出这棵树。

4、已知如图所示的有向图，请给出该图的： （1）顶点①②③的出度和入度：

（2）邻接表。

（3）基于（2）所得邻接表从1号顶点开始进行广度优先遍历的次序。

2007年

一、单项选择：

1、 以下关于数据结构的基本概念的叙述中哪一条是错误的？

A、数据元素是数据的基本单位

B、数据项是有含义的数据最小单位

C、数据结构概念包括的主要内容是数据的逻辑结构和数据的存储结构 D、数据的逻辑结构分为线性结构和非线性结构 2、以下关于数据结构的存储结构的叙述中哪一条是正确的？ A、数据的存储结构是数据间关系的抽象描述

B、数据的存储结构是逻辑结构在计算机存储器中的实现 C、数据的存储结构分为线性结构和非线性结构 D、数据的存储结构对数据运算的具体实现没有影响

3、在具有n个结点的单链表中，实现如下哪些操作，其算法的时间复杂度都是O（n）？ A、遍历链表和求链表的第i个结点 B、在地址为p的结点之后插入一个结点 C、删除开始结点 D、删除地址为p的结点的后继结点

4、在一个单链表HL（带头结点）中，若要向表头插入一个由指针p指向的结点，则执行 A、HL=p；pnext=HL; B、pnext=HL; HL=p;

C、pnext=HL;p=HL; D、pnext=HLnext;HLnext=p;

5、设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈为s2,s3,s4,s6,s5,s1，则顺序栈的容量至少应为 A、6 B、5 C、4 D、3 E、2

6、以下哪一个不是队列的的基本运算？

A、从队尾插入一个新元素 B、从队列中删除第i个元素 C、判断一个队列是否为空 D、读取队头元素的值 7、设n阶方阵是一个上三角矩阵，则需存储的元素个数为

A、n B、n*n C、n*n/2 D、n（n+1）/2

8、在顺序表（3，6，8，10，12，15，16，18，21，25，30）中，用二分法查找关键码值11，所需要的关键码比较次数为

A、2 B、3 C、4 D、5 9、设有字符序列（Q,H,C,Y,P,A,M,S,R,D,F,X），问新序列（F,H,C,D,P,A,M,Q,R,S,Y,X）是下列哪一个排序算法一趟扫描的结果？

A、起泡顺序 B、初始步长为4的希尔顺序

C、二路归并顺序 D、以第一元素为分界元素的快速排序

10、设有68个结点构成一棵完全二叉树，对该完全二叉树从根结点开始从上往下，自左向右进行编号（从1开始编号），则叶子结点的最小编号为 A、32 B、33 C、34 D、35 11、下列关于哈夫曼树的叙述，错误的是：

A、哈夫曼树根结点的权值等于所有叶结点的权值之和 B、具有你、个叶结点的哈夫曼树共有2n-1个结点

C、哈夫曼树是一棵二叉树，因此它的结点的度可以为0、1或2 D、哈夫曼树是带权外路径长度最短的二叉树

12、设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是 A、n在m右方 B、n在m左方 C、n是m祖先 D、n是m子孙

13、在有向图的邻接表存储结构中顶点v在表结点中出现的次数是

A、顶点v的度 B、顶点v的出度

C、顶点v的入度 D、依附于顶点v的边数

14、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的多少倍？ A、1/2 B、2 C、1 D、4 15、下面论述正确的是

A、在无向图中，边的条数是结点度数之和

B、在图结构中，结点可以没有任何前驱和后继

C、在n个结点的无向图中，若边数大于n-1，则该图必是连通图 D、图的邻接矩阵必定是对称矩阵 二、填空题

1、在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_____________。

2、在串S=“structure”中，以t为首字符的子串有__________个。

3、采用散列技术实现散列表时，需要考虑的两个主要问题是：构造________________和解决____________________。

4、索引顺序表上的查找分两个阶段：（1）_____________（2）_____________________。 5、设表中元素的初始状态是案件值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行排序（按递增顺序），____________最省时间，_____________最费时间。 6、设r指向单链表最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的条语句是_______________;_______________;____________________。

7、树有三种常用存储结构，即孩子链表法，孩子兄弟链表法和____________________。 8、数据的逻辑结构是从逻辑关系上描述数据，它与数据的_________无关，是于计算机的。

9、在下述算法中，标记为（4）、（5）的两个语句的时间复杂度分别为：______、______。 For(i=1;i<.=n;i++) (1) For(j=1;j<=n;j++) (2) {

c[i][j]=0; (3) for(k=1;k<=n;k++) (4)

c[i][j]=c[i][j]+a[i][k]*b[k][j]; (5) }

三、判断正误并说明理由 1、对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则改图一定是完全图。

2、队可以作为树的层次遍历的一种数据结构。

3、在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。 4、在索引顺序文件中插入新的记录时，必须复制整个文件。 5、在二叉树中插入新结点后则该二叉树便不再是二叉树。

四、综合应用题。

1、利用两个栈s1，s2模拟一个队列时，如何用栈的运算实现队列的插入，删除以及判队空运算。请简述算法思想。

2、一直一棵度为m的树中有N1个度为1的结点，N2个度为2的结点，…Nm个度为m的结点，问该树中有多少个叶子结点。请写出推导过程。

3、设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法： ①找出最小值结点，且打印该数值；

②若该数值是奇数，则将其与直接后继结点的数值交换； ③若该数值是偶数，则将其直接后继结点删除

4、某二叉树的前序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK

⑴试画出该二叉树

⑵设计一个算法，求二叉树的高度

⑶如果该二叉树是某片森林利用兄弟孩子法转化而来的，试画出该森林 5、已知一个图G的邻接矩阵

0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0

（1）请画出该图的逻辑结构

（2）如果该图采用逆邻接表存储方式，请画出其逆邻接表 （3）请画出该图的最小生成树

2008年

一、选择题

1、 有关线性表的说法不正确的是________

A. 线性表中的数据元素可以是数字、字符、记录、图片等不同类型。 B. 线性表中包含的数据元素个数不是任意的。

C. 线性表中的每个结点都有且只有一个直接前驱和直接后继。

D. 存在这样的线性表，表中各个结点都没有直接前驱和直接后继。

2、 在具有n个结点的单链表中，实现_____操作，其算法的时间复杂度都是O（n）。

A.遍历链表和求链表的第i个结点 B.在地址为p的结点之后插入一个结点

C.删除头结点 D.删除地址为p的结点的后继结点 3、下列不属于栈的应用的是___________

A.杨辉三角 B.表达式求解 C.数制转换 D.括号匹配

4、在具有n个元素的队列中，入队和出队操作的时间复杂度分别是_________

A.O（log2n）,O(n) B.1,O(log2n) C.O(n),O(n) D.1,1 5、设有两个串S1和S2，求S1在S2中首次出现的位置的运算叫做__________

A.求子串 B.模式匹配 C.串替换 D.串连接

6、设T1是一棵树，T2是对应于T1的二叉树，则T1的先根序列遍历和T2的________

次序遍历相同 A.先根 B.中根 C.后根 D.不存在

7、在一棵二叉树的先序序列、中序序列中，所有叶子结点的先后顺序___________ A.都不相同 B.完全相同 C.先序与中序相同，而与后序不同 D.中序与后序相同，而与先序不同

8、设森林F中有三棵树，第一、二、三棵树的结点个数分别为m1、m2、m3，则与森林F

对应的二叉树根结点的右子树上的结点个数是_____________ A.m1 B.m1+m2 C.m3 D.m2+m3

9、带权有向图G用邻接矩阵A存储，则顶点I的入度等于A中___________ A.第I行非无穷元素之和 B.第I列非无穷元素之和

C.第I列非零且非无穷元素个数 D.第I行非零且非无穷元素个数 10、在有N个顶点的有向图中，每个顶点的度最大可达____________

A.2*N B.2(N-1) C.N*N D.N(N+1)

11、任一个AOE网中，至少有__________条关键路径，且是从源点到汇点的路径最长的一条。

A.1 B.2 C.3 D.4 12、一个具有n个顶点e条边的无向图采用邻接表表示，则表向量的大小为_____________ A. n-1 B.n+1 C.n D.n+e

13、若对任意非空二叉树，要设计出其后根遍历的非递归算法而不使用堆栈结构，最适合的方法是对该二叉树采用___________存储结构

A.三叉链表 B.二叉链表 C.顺序 D.索引

14、若一棵哈夫曼树有20个度为2的结点，则它共有_________个叶结点。 A.19 B.20 C.21 D.22 15、下属描述正确的是____________

A.顺序存储方式的优点是存储密度大且插入、删除运算效率高

B.链表的每个结点中都恰好包含一个指针

C.线性表的顺序存储结构优于链式存储结构

D.顺序存储结构属于表态结构，而链式存储属于动态结构 二、填空题

1、数据的逻辑结构被分为：__________、____________、___________、__________等四种，而数据的存储结构被分为：_________、___________、索引结构，散列结构等四种。 2、若线性表的长度为n，若要在表的第i个位置插入一个数据元素，则i取值范围是__________，若在第i个位置做的是删除操作，则i的取值范围是_____________。 3、不同的编译语言中，字符串结束定义是不一样的。在C语言中，要存储一个包含10个

字符的字符串，至少需要声明大小为_________的字符数组。 4、按照树的定义，具有3个结点的二叉树有__________种形态。

5、请读下列程序，该程序是在单链表中删除一个结点的算法，为空出的地方填上正确的语句。 Void demo2(LinkList head,ListNode *p)

{ //head是带头结点的单链表，删除P指向的结点 ListNode *q=head;

While(_____________)q= q->next; If(q) Error(“*p not in head”); ______________________; ______________;

} 三、判断题

1、数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。 2、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法同样结点的顺序表的平均搜索时

间。 3、若有一个结点是二叉树中某个子树的中序遍历结构的最后一个结点，则它一定是该子树

的前序遍历结果序列的第一个结点。 4、任何一个关键活动提前完成，那么整个工程将会提前完成。

5、起泡顺序是对快速排序的一种改进，因此在性能上前者比较后者要高。 四、综合题

1、写一算法，该算法依次从外部获取n个元素，然后按照相反的方向依次输出这批数据，

请写出该算法可能涉及到的数据元素结构定义及相应算法。 2、已知长度为n，并且按值有序的线性表A采用顺序存储结构（假设每个数据元素为一非零的正整数），写一时间效率较高的算法，删除数据元素[x,y]之间的所有元素。 3、已知一个无向图的邻接表为：

（1）、画出这个图： （2）、以V1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。 4、现有一如右图示的森林，请：

（1）、把该森林转换成对应的二叉树；

（2）、画出（1）得到的二叉树的顺序存储结构；

5、已知如右图所示的有向图，请给出该图的：

（1）、在下表中填写各个顶点的入度和出度；

（2）、邻接矩阵； （3）、邻接表； （4）、强连通分量。 顶点 入度 出度 1 2 3 4 5 6

6、已知串s=“（xyz）+*”，串t=“(x+z)*y”，试写一个函数利用串的基本运算将s转化t

7、试编写一个函数计算n！*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0≤n≤arraySize，若设计算机中允许的整数的最大值为maxInt，则当n> arraySize或者对于某一个k（0≤k≤n），使得k！*2k>maxInt时，应按出错处理。可有如下三种不同的出错处理方式：

（1）、用error及exit（1）语句来终止执行并报告错误； （2）、用返回整数函数值0，1来实现算法，以区别是正常返回还是错误返回； （3）、用函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。用你认为是最好的方式实现它。