数据结构(C++)模拟试题

.

模拟试题3

一．选择题

1.当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ）

2

A.n-1

2

n C. 2log

2

n D.n

冒泡排序

选择排序

插入排序

堆排序

归并排序

快速排序

希尔排序

2

n

n

n

2

2

2

nlog n

nlog2n

2

n

n

2

2.以下时间复杂性不是O(n)的排序方法是( )

A.直接插入排序 B.二路归并排序 C.冒泡排序 D.直接选择排序

3.．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。

A.顺序存储 B 链式存储

C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序

4.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为

84的结点时，经（ ）次比较后查找成功。

A.2 B. 3 C. 4 D. 12

5.静态查找表与动态查找表两者的根本差别在于( )…………………………………………….

A.逻辑结构不同 B.存储实现不同

C.施加的操作不同 D.数据元素的类型不同

6．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为

2

A.O（n） B. O(nlog

2

n) C. O（n） D.O(log

2

n)

7.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。

A. 5 B. 6 C. 7 D 8

8.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。

A.0．5 B.1 C.2 D.4

9.深度为6的二叉树最多有( )个结点.

A.64 B.63 C.32 D.31

10．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那

么编号为41的双亲结点编号为 ( )

A.42 B.40 C.21 D.20

11.已知某二叉树的后序遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（ ）

12.设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( )

A.都不相同 B.完全相同

C.先序和中序相同，而与后序不同 D.中序和后序相同，而与先序不同

13．如果以链表作为栈的存储结构，做退栈操作时( )

A.必须判别栈是否满 B.必须判别栈是否空

C.判别栈元素的类型 D.对栈不做任何操作

14．链栈与顺序栈相比，有一个比较明显的优点即（ ）

A.插入操作更方便 B. 通常不会出现栈满的情况

.

.

C.不会出现栈空的情况 D. 删除操作更方便

15.线性结构中的一个结点代表一个（ ）

A. 数据元素 B. 数据项 C. 数据 D. 数据结构

二．填空题

1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方

法是________的，否则称为________的。

2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。

3.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。

4.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。

5.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值________于其左孩子（及其子

孙）的键值且________于其右孩子（及其子孙）的键值。

6.中根遍历一棵二叉排序树所得的结点访问序列是键值的________序列。

7.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。

8.采用散列技术时需要考虑的两个主要问题是：一、________？二、________？

9.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧度数为________。

10.遍历图的基本方法有________优先搜索和________优先搜索两种。

11.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中的任意两个顶点v

i

,v

j

∈V，

且v

i

和v

j

都是连通的，则称G为________。

12.二叉树第i(i>=1)层上至多有______个结点。

13.深度为k(k>=1)的二叉树至多有______个结点。

14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的

________个指针域为NULL。

15．有m个叶子结点的哈夫曼树，其结点总数为________。

16．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。

17．队称为___________线性表。

18.从某种意义是说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个__________构成，数

据元素可由若干个__________构成。

19.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(________)线性阶O(___________)、平方阶

O(___________)、和指数阶O(___________)。

20.线性结构的基本特征是若至少含有一个结点，则除起始结点没有直接______外，其他结点有且仅有一个直接______;

除终端结点没有直接______外，其它结点有且仅有一个直接______.

三．名词解释题

1.排序 2.堆 3. ..查找长度 4.无向完全图 5.有向完全图

6. 二叉树 7. 满二叉树 8..栈 9..队列 10.链表

四．简答题

1.

2.

3.

4.

5.

.

什么是二叉排序树?

什么是顺序表?

什么叫稀疏矩阵?

静态查找表与动态查找表的区别是什么?

什么叫无向图?

.

五．解答题

1．判断下列两序列是否为堆？若不是，按照建堆的思想把它调整为堆，并用图表示建堆的过程。

（1）（3，10，12，22，36，18，28，40）；

（2）（5，8，11，15，23，20，32，7）。

2．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排序和冒泡排序每趟的结果。

3.对长度为20的有序表进行二分查找，请画出它的一棵判定树，并求等概率情况下的平均查找长度。

六．算法设计题

1.找出数组]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。

2..在数组]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输出0作为标志。

3.设有数组A[n],n>1,试设计一个算法,求数组A[n]的逆序。

模拟试题4

一、单项选择题

1.下面程序段的时间复杂度是( )

for(i=0;i

for(j=1;j

A[i][j]=0；

A.O(n) B.O(m+n+1) C.O(m+n) D.O(m*n)

2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( )

A.p=p->next; B.p->next=p->next->next;

C.p->next=p; D.p=p->next->next;

3.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head,则( )

A.p指向头结点 B.p指向尾结点

C.*p的直接后继是头结点 D.*P的直接后继是尾结点

4.判定“带头结点的链队列为空”的条件是( )

A. ==NULL B. ==NULL

C. == D. !=

5.设有两个串T和P，求P在T中首次出现的位置的串运算称作( )

A.联接 B.求子串 C.字符定位 D.子串定位

6.广义表A=(a,(b),(),(c,d,e))的长度为( )

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

7.一棵含18个结点的二叉树的高度至少为( )

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

8.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为( )

9.无向图中一个顶点的度是指图中( )

A.通过该顶点的简单路径数 B.与该顶点相邻接的顶点数

C.通过该顶点的回路数 D.与该顶点连通的顶点数

10.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。

A.0．5 B. 1 C. 2 D.4

11.在下列排序方法中，平均时间复杂度为O(nlogn)且空间性能最好的是( )

A.快速排序 B.堆排序 C.归并排序 D.基数排序

.

.

12.已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两

两归并的结果是( )

A.{25,36,48,72,23,40,79,82,16,35} B.{25,36,48,72,16,23,40,79,82,35}

C.{25,36,48,72,16,23,35,40,79,82} D.{16,23,25,35,36,40,48,72,79,82}

13.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值

为84的结点时，经（ ）次比较后查找成功。

A.2 B. 3 C. 4 D. 12

14．以下说法正确的是 （ ）

A.查找表中数据元素的任何数据项都可以作为关键字。

B.采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快

C.二叉排序数的查找和二分查找时间的性能相同。

D.最佳二叉排序树一定是平衡二叉树

15.倒排文件的主要优点是( )

A.便于进行插入和删除运算 B.便于进行文件的恢复

C.便于进行多关键字查询 D.节省存储空间

二、填空题

1.抽象数据类型的特点是将____________和____________封装在一起，从而现实信息隐藏。

2.从顺序表中删除一个元素时，表中所有在被删元素之后的元素均需____________一个位置。

3.在队列中，允许进行插入操作的一端称为____________，允许进行删除操作的一端称为____________。

4.对于顺序栈而言，在栈满状态下，如果此时再做进栈运算，则会发生“________”。

5.设S1="good",S2=" ",S3="book"，则S1，S2和S3依次联接后的结果是____________。

6.假设三维数组A[10][9][8]按行优先顺序存储，若每个元素占3个存储单元，且首地址为100，则元素A[9][8][7]

的存储地址是____________。

7.已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点，则该树中含有的叶子结点的数目为

____________。

8.能够成功完全拓扑排序的图一定是一个____________。

9.如果在排序前，关键字序列已接近正序或逆序，则在堆排序和快速排序两者之中，选用____________较为适当。

10.散列文件删除记录时，仅需对被删记录________即可。

三、解答题

1.假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这

6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分

别写出每个字符对应的编码。

2.已知两个4×5的稀疏矩阵的三元组表分别如下：

0

1

2

3

1 4 16

2 2 18

3 4 －25

4 2 28

0

1

2

3

4

1

2

2

3

4

1

2

5

4

2

32

－22

69

25

51

请画出这两个稀疏矩阵之和的三元组表。

3.从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。

.

.

(1)画出该二叉排序树

(2)画出删去该树中元素值为90的结点之后的二叉排序树。

四、算法设计题

1.假设以带头结点的单循环链表作非递减有序线性表的存储结构。请设计一个时间复杂度为O(n)的算法，删除表中所

有数值相同的多余元素，并释放结点空间。例如：

(7，10，10，21，30，42，42，42，51，70)

经算法操作后变为

(7，10，21，30，42，51，70)

2．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表示。

3．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以及花括号与“{”和“}”，

且这三种括号可按任意的次序嵌套试用，如（.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈

的运算编写判断给定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。

内蒙古财经学院期末考试《数据结构》试卷（A）

一、 单项选择题（1×10=10分）：

１、对于一个N个顶点的图,若采用邻接矩阵存储,则矩阵的大小为______________

2

(A) N (B) N (C) N+1 (D) N-1

２、每次从无序表中取一个元素,把它插到有序表的合适位置,此种排序为______________;

每次从无序表挑选出一个最大或最小的,把它与第一个位置或最后一个位置交换,此种排序为______________;每

次比较两个相邻的元素,若出现逆序,则交换这两个元素的位置, 此种排序为______________;每次把相邻的两个

有序表合成一个有序表的方法是________________.

(A) 堆排序 (B)快速排序 (C)插入排序 (D) 交换排序

(E) 基数排序 (F)冒泡排序 (G)希尔排序 (H)归并排序

３、解决散列中出现冲突问题的常采用的方法是_________________

(A)数字分析法 、除留余数法、平方取中法 (B) 数字分析法 、除留余数法、线性探测法 (C)数字分析法、线

性探测法、双散列法 (D) 线性探测法、二次探测法、链地址法

４、已知某二叉树先序遍历序列为ABDCE则它可能的中序遍历序列为 。

(A)BCADE (B)CBADE

(C)BEACD (D)BDAEC

5、若树中用一个分支把两个结点连接起来，则 。

（A）不一定出现环 （B）一定出现环

（C）使树的度数增一 （D）前面说法都不正确

６、设散列地址空间为0---M-1， K为表项的关键码，散列函数采用除留余数法，HASH（K）= K % P 。为减少冲突

的频率，一般P为__________________

(A) M (B) 小于M的最大质数 (C) 大于M的最大质数 (D) 小于M的最大合数

.

.

７、在一般情况下，将递归转化为非递归算法应该设置（ ）

（Ａ）栈 （Ｂ）队列 （Ｃ）栈或队列 （Ｄ）数组

二、判断题：（1×10=10分）

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

点。（ ）

２、邻接表只能用于有向图的存储, 邻接矩阵对于有向图和无向图的存储都适用.

（ ）

３、设N为哈夫曼树的叶子结点数目，则该哈夫曼树共有2*N+1个结点。 （ ）

４、二叉树的中序遍历的和后序遍历可以唯一决定一棵二叉树 （ ）

５、线性表的逻辑顺序与物理顺序总是一致的。 （ ）

６、带表头的单链表比不带表头的单链表操作更简单。 （ ）

７、有N ( N > 1 ) 个顶点的无向连通图至少有N-1条边. （ ）

８、外部排序只能选用归并排序 （ ）

９、快速排序和冒泡排序都是不稳定排序 （ ）

１０、二叉树是特特殊的树 （ ）

四、简答题：（30分）

1、线性表有两种存储结构：一是顺序表，二是链表。试问：

（1）如果有n个线性表同时存在，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情

况下，应选用哪种存储结构？为什么？

（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应选用哪种

存储结构？为什么？（5分）

2、采用折半查找方法进行查找的数据文件应满足什么条件？（5分）

3、设双向循环链表中结点的结构为（data , llink, rllink）,且不带表头结点。若想在指针p所指结点之后插入指

针s 所指结点，则应执行怎样的操作？（5分）

4、已知一棵二叉树的前序便历的结果是ABECDFGHIJ，中序便历的结果是EBCDAFHIGJ，试画出这棵二叉树。（5分）

5、给定权值集合{15，03，14，02，06，09，16，17}，构造相应的霍夫曼树，并计算它的带权外部路径长度。（5分）

五、由如下的网络邻接矩阵，画出一棵最小生成树。（7分）

六、给定一个关键字序列﹛24，19，32，43，38，6，13，22﹜，请写出快速排序第一趟的结果，堆排序时所建的初始

堆，归并排序的全过程。然后回答上述三种排序方法中哪一种使用的辅助空间最少？在最坏情况下哪一种方法的时间

复杂度最差？（10分）

七、编写程序（33分）

１、统计二叉树结点的个数的算法。（11分）

２、设一个带表头结点的单链表中所有元素结点的数据值无序排列，试编写一个函数，删除表中值为X的元素（若存

在）。（12分）

3、写出冒泡排序算法．（10分）

注：试卷与答题纸一起交

.

.

内蒙古财经学院期末考试

《数据结构》试卷(A)答案

一、 单项选择题：

１、(A)２、(CDFH)３、D４、D５、C６、B ７、A

二、判断题：

１、 ( X ) ２、 ( X ) ３、 （ V ）

４、 （ X ）５、 （ V ）６、 （ V ）

７、 （ V ）８、 （ V ）９、 （ X ）

１０、 （ V ）

四、简答题：

１、(1)链表 (2) 顺序表

２、顺序存储,且有序

３、s->rlink=p->rlink; s->llink=p;

p->rlink->llink=s; p->rlink=s;

4、

5、wpl=229 树的根权值为82

五、包含 6 7 11 10 12 COST=46

六、快速排序的第一趟结果 22 19 6 13 24 32 43 38

小顶堆 6 19 13 22 38 32 24 43

大顶堆 43 38 32 22 24 6 13 19

归并结果 19 24 32 43 6 38 13 22

6 13 19 22 24 32 38 43

七、：

1、template class BinTreeNode{

friend class BinTree;

Type data;

BinTreeNode *leftchild,*rightchild;

};

template class BinTree{

BinTreeNode *root;

public:

BinTree();

int numyezi();

};

template int BinTree::numyezi(){

if( root==NULL) return 0;

else if(root->leftchild==NULL&&root->righchild==NULL)

return 1;

else { int m=numyezi(root->leftchild);

int n=numyezi(root->righchild);

return m+n+1;}

.

.

}

2、template class ListNode{

friend class List;

type data;

ListNode *link;

};

template class List{

ListNode *first;

public:

List();

void dele(int min,int max);

};

template void List::dele(int min,int max)

{ if(min

ListNode *p=first->link,*pre=first;

while(p)

{ if(p->datadata>min)

{pr->link=p->link;

delete p;

p=pre->link;

}

else{ pre=p;p=p->link;}

}

}3、

template

void dataList :: BubbleSort ( ) {

int pass = 1; int exchange = 1;

while ( pass < CurrentSize && exchange ){

exchange = 0; //标志置为0,假定未交换

for ( int j = CurrentSize-1; j >= pass; j-- )

if ( Vector[j-1] > Vector[j] ) { //逆序

Swap ( Vector[j-1], Vector[j] );

//交换

exchange = 1;

//标志置为1,有交换

}

pass++;

}

}

.

.

.