《数据结构》复习题.doc

《数据结构》复习题

《数据结构》复习题

（含部分参考答案版）

一、单项选择题

1. 按照数据逻辑结构的不同，可以将数据结构分成C 。

A. 动态结构和静态结构

B. 紧凑结构和非紧凑结构

C. 线性结构和非线性结构

D. 内部结构和外部结构

2. 下列关于数据结构的叙述中正确的是A 。

A. 数组是同类型值的集合

B. 递归算法的程序结构比迭代算法的程序结构更为复杂

C. 树是一种线性的数据结构

D. 用一维数组存储二叉树，总是以先序顺序遍历各结点

3. 在计算机的存储器中表示时，物理地址与逻辑地址相同并且是连续的，称之为B

A.逻辑结构

B.顺序存储结构

C.链式存储结构

D.以上都不对

4. 以下关于算法特性的描述中，B 是正确的。

（1）算法至少有一个输入和一个输出

（2）算法至少有一个输出但是可以没有输入

（3）算法可以永远运行下去

A. （1）

B. （2）

C. （3）

D. （2）和（3）

5. 对顺序存储的线性表（a1,a2,…,an）进行插入操作的时间复杂度是C 。

A.O(n)

B. O(n-i)

C. (n/2)

D. O(n-1)

6. 链表不具有的特点是A 。

A.可随机访问任一元素

B.插入和删除时不需要移动元素

C.不必事先估计存储空间

D.所需空间与线性表的长度成正比

7.线性链表中各链结点之间的地址C 。

A.必须连续

B.部分地址必须连续

C.不一定连续

D.连续与否无关

8. 以下关于链式存储结构的叙述中，C 是不正确的。

A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构

B.逻辑上相邻的结点物理上不必邻接

C.可以通过计算直接确定第i个结点的存储地址

D.插入、删除操作方便，不必移动结点

9. 设依次进入一个栈的元素序列为d, a, c, b,得不到出栈的元素序列为D 。

A. dcba

B. acdb

C. abcd

D. cbda

10. 将新元素插入到链式队列中时，新元素只能插入到B 。

A. 链头

B. 链尾

C. 链中

D. 第i个位置，i大于等于1，大于等于表长加1

11. 设栈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

12.下面D 是‘abcd321ABCD’的子串。

A. abcd

B. 321ab

C. ‘abc ABC’

D. ‘21AB’

13.假设8行10列的二维数组A[1…8，1…10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3，5]的地址与以列序为主序时C

元素相同。

A. a[7，3]

B. a[8，3]

C. a[1，4]

D. ABC都不对

14. 数组A[0…5，0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址为A 。

A. 1175

B. 1180

C. 1205

D.1210

15.下列广义表中，长度为3的广义表为B 。

A.（a,b,c,( )）

B. ((g),(a,b,c,d,f),( ))

C. (a,(b,(d)))

D. ((( )))

16. 以下关于广义表的叙述中，正确的是A 。

A. 广义表是0个或多个单元素或子表组成的有限序列

B. 广义表至少有一个元素是子表

C. 广义表不可以是自身的子表

D. 广义表不能为空表

17.若树T有a个度为1的结点，b个度为2的结点，c个度为3的结点，则该树有D 个叶结点。

A. 1+2b+3c

B. a+2b+3c

C.2b+3c

D. 1+b+2c

18.若一棵二叉树有102片叶子结点，则度二叉树度为2的结点数是B 。

A. 100

B. 101

C. 102

D. 103

19. 在有n 个叶子结点的霍夫曼树中，其结点总数为：。

A. n

B. 2n

C. 2n +1

D. 2n - 1

20.具有12个结点的完全二叉树有B 。

A. 5个叶子结点

B. 5个度为2的结点

C. 7个分支结点

D. 2个度为1的结点

21.设结点x和y是二叉树中的任意两结点，若在先根序列中x在y之前，而后根序列中x 在y之后，则x和y的关系是C 。

A. x是y的左兄弟

B. x是y的右兄弟

C. x是y的祖先

D. x是y的后代

22. 先序遍历序列与中序遍历序列相同的二叉树为。

A. 根结点无左子树的二叉树

B.根结点无右子树的二叉树

C. 只有根结点的二叉树或非叶子结点只有左子树的二叉树

D. 只有根结点的二叉树或非叶子结点只有右子树的二叉树

23.若二叉树T的前序遍历序列和中序遍历序列分别是bdcaef和cdeabf，则其后序遍历序列为A 。

A. ceadfb

B. feacdb

C. eacdfb

D. 以上都不对

24.设无向图的顶点个数为n，则该图最多有C 条边。

A. n-1

B. n(n-1)

C. n(n-1)/2

D. n

25.对于一个有n个顶点和e条边的无向图，若采用邻接表表示，邻接表中的结点总数是C 。

A. e/2

B. e

C. n+2e

D. n+e

26. 无向图G=（V，E），其中V=｛a,b,c,d,e,f｝,E=｛(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)｝。

对该图进行深度优先遍历，下面不能得到的序列是D 。

A. acfdeb

B. aebdfc

C. aedfcb

D. abecdf

27.在下述排序方法中，不属于内排序方法的是C 。

A. 插入排序法

B. 选择排序法

C. 拓扑排序法

D. 归并排序法

28. 直接插入排序在最好情况下的时间复杂度为B 。

A. O(log2n)

B. O(n)

C. O(nlog2n)

D. O(n2)

29.对有n个记录的表作快速排序，在最坏情况，算法的时间复杂度是D 。

A. O(n3)

B. O(n)

C. O(nlog2n)

D. O(n2)

30.下面的排序算法中，稳定是A 。

A. 直接插入排序法

B. 快速排序法

C. 直接选择排序法

D. 堆排序法

二、填空题

1. 一个算法具有5个特性：、、、有零个或多个输入，一个或多个输出。

2. .设数组a[1…50，1…80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为9174 ；若以列序为主序顺序存储，则元素a[45，68]的存储地址为8788 。

3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

4.两个字符串相等的充分必要条件是长度相等且对应位置上的字符相等。

5. 字符串“abcd”中共有个长度大于0的字串。

6. 广义表list=（5，（3，2，（14，9，3），（），4），2，（6，3，10））的长度及深度分别

为和。

7.若二叉树的先序序列和后序序列相反，则该二叉树一定满足只有一个叶子结点。

8.若无向图满足有n-1条边的连通图，则该图是树。

9.若无向图中有n个顶点，则其边数最少为n-1 ，最多为n(n-1)/2 。

10.堆排序的时间复杂度和空间复杂度分别为O(nlog2n) 和O(1) 。

三、名词解释

（1）抽象数据类型（2）算法及其特性（3）串的模式匹配（4）优先级队列

（5）完全二叉树（6）堆（7）Huffman编码（8）Huffman树

（9）连通分量及重连通分量（10）最小生成树（11）克鲁斯卡尔算法

（12）普里姆算法（13）希尔排序（14）快速排序

（15）教材等等相关名次解释题

四、简答题

1. 请对线性表进行顺序存储和链式存储的特点作比较。（西电2004年考研试题）

2. 单链表为什么要引入头结点？

3.线性表的链式存储结构有单链表、循环链表、双向链表，试问它们各有什么优点和缺点？参考答案：

单链表的优点是空间动态分配，插入和删除时不需要移动数据，缺点是不能随机访问数据。和其它两种相比，它还节省了空间。

循环链表除了具有单链表的优点外，它从任意结点出发可以找到其它结点。缺点同单链表的缺点。

双向链表除了具有循环链表的优点，它还可以方便地找到某个结点的前驱。缺点是增加了空间开销。

4.内存中一片连续空间（不妨假设地址从1到m），提供给两个栈使用，怎样分配这部分存

储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。

5. 假设有一个适当大小的栈S，输入栈的序列为A，B，C，D，E。

问：（1）能否得到下列的输出序列：①B，C，D，E，A；②E，A，B，C，D；

③E，D，C，B，A。

（2）写出所有可能正确的输出序列（至少5种）。

6.用向量表示的循环队列的队首和队尾位置分别为1和max_size，试给出判断队列为空和为满的边界条件。

参考答案：

队空条件为max_size==1;

队满的条件为（max_size+1）%MAXSIZE.

7. 设一棵二叉树后序遍历序列为DGJHEBIFCA，中序遍历序列为DBGEHJACIF，要求：（1）画出该二叉树；

（2）写出该二叉树的先序遍历序列；

（3）画出该二叉树对应的森林。

8.对二叉树中的结点按层次顺序（每一层自左向右）进行的访问操作称为二叉树的层次遍历。现已知一棵二叉树的层次序列为AEBGFDIMH，中序遍历序列为GEFAMDBHI。请画出该二叉树并写出其先序序列。若将该二叉树看作是一个森林的孩子—兄弟表示，请画出该森林。（西电2004年考研试题）

9. 已知某通信电文仅由A、B、C、D、E、F这6个字符构成，其出现的频率分别为23、5、14、8、25、7，请给出它们的霍夫曼树及其对应的霍夫曼编码。

10.给定下列图G用两种不同表示法画出该图的存储结构图。

11. 针对上图分别用卡鲁斯卡尔及普里姆算法给出该图的最小生成树，画出其逻辑结构。

12.总结直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序、简单选择排序、锦标赛排序、堆排序及归并排序等在最好情况下、最坏情况及平均的时间复杂度，辅助空间复杂度及稳定性。

13.判断下面的每个结点序列是否表示一个堆，如果不是堆，请把它调整为堆。

（1）100，90，80，60，85，75，20，25，10，70，65，50

（2）100，70，50，20，90，75，60，25，10，85，65，80

14.已知一序列（12，70，33，65，24，56，48，92，86，33），问该序列是否是堆？如果不是，则把它调整为小顶堆。并问把该序列调整为堆共需要多少次元素间的比较？多少次元素间的交换。（西电2005年考研试题）

15.试为下列情况选择合适的排序算法：（西电2006年考研试题）

（1）n=30，且要求最坏情况下速度最快；

（2）n=30，且要求既要快，又要排序稳定；

（3）n=2000，要求平均情况下速度最快；

（4）n=2000，要求最坏情况下速度最快，又要节省存储空间。

五、算法设计题

1. 实现一个算法，完成在不带表头结点的单链表第i个结点之前插入新元素x的操作。（教材P74页）

2.（a）实现一个函数，完成在带表头结点的双向循环链表中，建立一个包含有值value的新结点并将其插入到当前结点之后。（教材P91页）

（b）实现一个函数，完成在带表头结点的双向循环链表中删除当前结点，同时让当前指针

指到链表中下一个结点位置。（教材P91页）

3.（a）实现一个函数完成删除链式栈顶结点，返回被删栈顶元素的值。（教材P107页）（b）实现一个函数完成删除链式队列队头结点，并返回被删对头元素的值。（教材P117页）

4.对二叉链表，实现一个函数Parent(*BinTreeNode*start, *BinTreeNode*curent)从结点start 开始，搜索结点current的双亲结点，并返回其地址，否则返回NULL。（教材P171页）

5. 若用二叉链表作为二叉树的存储表示，试针对下列问题编写递归算法：

（1）统计二叉树中叶子结点的个数；

（2）交换每个结点的左子女和右子女。

6.熟练掌握直接插入排序、折半插入排序、希尔排序、起泡排序、快速排序等其它排序的算法

7.若以域变量rear和length分别指示循环队列中队尾元素的位置和队列中元素的个数。请完成下面的入队列和出队列的算法：（西电2004年考研试题）

#define MAXQSIZE 100 //最大队列长度

Type struct｛

Qelemtype *base; //base为队列所在区域的首地址

int length; //队列长度

int rear; //队尾元素位置

｝SqQueue;

Status EnQueue(SqQueue &Q, Qelemtype e)

｛

if ( ①) return ERROR; // 队列满，无法插入

Q.rear= ②; //计算元素e的插入位置

③= e; //在队尾加入新的元素

Q.length++; //队列长度加1

return OK;

｝

Status DeQueue(SqQueue &Q, Qelemtype &e) //删除对头元素，并用e带回其值

｛

if ( ④)return ERROR; //队列满

e=Q.base[ ⑤]; //取队头元素

Q．length --; //队列长度减1

return OK;

｝

8.请运用快速排序思想，设计递归算法实现求n（n＞1）个不同元素集合中的第i（1≤i≤n）小元素。（西电2004年考研试题）

9.阅读下列函数说明及相应代码，在空白处填入相应语句。

(西电2005年考研试题)

[函数1]

函数palinddrome(char s[])的功能是：判断字符串s是否为回文字符串，若是，则返回0，否则返回-1。若一个字符串顺读和倒读都一样时，称该字符串是回文字符串，例如：“LEVEL”是回文字符串，而“LEV AL”不是。

Int palindrome (char s[])

{char *pi, *pj;

Pi = s; pj =s + strlen(s) –1; //*strlen(s)函数用于求得串s的串长

While（pi＜pj && ①）{

Pi ++; pi - - ;

}

if ( ②)return - 1;

else return 0;

}

[函数2]

函数insert_sort(int a[],int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。

V oid insert_sort(int a[], int count)

{ int i, j, t;

for (i=1;i＜count;i++){//控制a[i]，…a[count-1]的比较和插入

t = a[i];

j= ③;

while (j≥0&&t＜a[j]){ //在有序部分寻找元素a[i]的插入位置

④;

j - -;

}

⑤;

}

}

10. 假设以数组seq[0…m-1]存放循环队列中的元素，同时设变量rear和quelen分别指示循环队列中的队尾元素的位置和内含元素的个数。(西电2006年考研试题)

请给出：

（1）给出循环队列的队满条件和队空条件；

（2）写出相应的入队列和出队列的算法，并分别分析其时间代价；

（3）如果用数组sequ[m…n]来存放循环队列中的元素，则（2）中的入队列和出队列的算法中的哪些语句要修改？如何修改？

本文来源于血色浪漫营https://www.wendangku.net/doc/9215182031.html,/blog/ , 原文地址：https://www.wendangku.net/doc/9215182031.html,/blog/post/531.html

数据结构模拟题(开卷)

《数据结构》模拟题（补） 一．单项选择题 1.在线性表的下列存储结构中，读取元素花费时间最少的是【】。 A．单链表B．双链表C．顺序表D．循环链表 2.设计一个判定表达式中左、右括号是否配对出现的算法，采用【】数据结构最佳。 A．集合B．线性表C．队列D．栈 3.n个结点的线索二叉树上含有的线索数为【】。 A．2n B．n-1 C．n D．n+1 4.设广义表D=(a,(b,c)),则tail(D）=【】。 A．b,c B．(b,c) C．((b,c)) D．c 5.由4个结点可以构造出【】种不同的二叉树。 A．12 B．13 C．14 D．15 6.在栈中，出栈操作的时间复杂度为【】。 A．O(1) B．O(n) C．O(log2n) D．O(n2) 7.假设Q[0..len-1]表示循环队列，f为队头指针，r为队尾指针，则进队操作语句是【】。 A．f=f+1 B．r=r+1 C．f=(f+1)%len D．r=(r+1)%len 8.一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为【】。 A．n*n B．n*n/2 C．n*(n+1)/2 D．(n+1)*(n+1)/2 9.队列操作的原则是【】。 A．进优于出B．出优于进C．先进先出D．后进先出 10.下列数据结构中，【】是非线性数据结构。 A．栈B．串C．队列D．树 11.两个指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱，则【】。 A．p==q B．q->next=p C．p->next=q D．p->next=q->next 12.数组A中，每个元素的长度为4个字节，行下标i从1到5，列下标j从1到4，从首 地址SA开始连续存放在存储器内，该数组按行存放时，元素A[3][2]的起始地址为【】。 A．SA+20 B．SA+36 C．SA+40 D．SA+45 13.已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为d1， 则第i个结点的地址为【】。 A．d1+(i-1)*m B．d1+i*m C．d1+(i+1)m D．d1-i*m 14.分析下列算法suanfa1(n)的时间复杂度是【】。 void suanfa1(int n) { int i,j,x=1； for(i=0；i

信息技术模拟试题

信息技术模拟试题 篇一：2015信息技术模拟试题-2 2015年沈阳市省普通高中学生学业水平模拟考试（二） 信息技术 （本试卷分为第I卷和第II卷，满分100分，考试时间为50分钟） 注意事项： 1. 答卷前，考生务必将自己的姓名、准考证号填写在答题卡上。 2. 答案一律写在答题卡上，写在本试卷上无效。考试结束后，将本试卷和答题卡一并交回。 3. 做第I卷答选择题时，选出每小题答案后，用2B铅笔把答题卡上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。 第I卷选择题 一、单项选择题（本大题包括15小题，每小题3分，共45分） 1. 从信息的一般特征来说，以下说法不正确的是（） A．信息不能独立存在，需要依附于一定的载体。 B．信息可以转换成不同的载体形式而被存储和传播 C．信息可以被多个信息接受者接受并且多次使用 D．同一个信息不可以依附于不同的载体。 2.下列用于管理、监控、维护计算机正常工作，实现用户操作的计算机软件是（）。 字处理软件操作系统安全卫士 D. 瑞星杀毒软件

3. 城市大部分的十字路口都采用电子警察拍照的方式来约束闯红灯的现象，这个拍照的过程属于（） A．信息处理B．信息采集C．信息加工D．信息储存 4.在ASCII字符编码表中，字符“A”的ASCII码是65，字符“d”的ASCII码是（）。 5. 在“资源管理器”窗口中，若要选定多个不连续排列的文件，下列操作中正确的是（）。A.按住Ctrl键，单击文件逐个选定 B.按住Shift键，单击文件逐个选定C.按住Alt键，单击文件逐个选定D.按住Shift键，右击文件逐个选定 6.在研究性学习过程中，同学间可以通过互联网进行讨论与交流，下列可以进行实时交流的工具是（）。 A. E_ 7.下面是收集到的素材文件①紫荆花.JPG、②月光曲.WAV、③按钮.PSD、④荟萃园.BMP、⑤健康讲座.MPG⑥生物实验.SWF，可以用Photoshop CS 进行加工处理的文件是（）。 A. ①②⑤ B. ①③④ C. ②⑤⑥ D.③④⑥ 8． Word文档编辑时，对于插入文档中的图片不能进行的操作是( )。 A.放大或缩小 B. 剪裁 C.移动 D.修改图片中的图形 9．在Excel中，数据筛选的功能是（）。 A．只显示符合条件的数据，隐藏其它 B．删除掉不符合条件的数据 C．对工作表数据进行分类D．对工作表数据进行排序 10．要

数据结构试卷带答案

数据结构试卷（一） 一、选择题（20分） 1．组成数据的基本单位是（ 1.C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（D）的逻辑结构。 (A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（.A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈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 7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（8.B (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（B）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（B ）的空间复杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元 素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。 2.设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________， 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指 针域，__________个空指针域。 4.设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编 号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构模拟试题及答案

数据结构模拟试题一 一、判断题（每小题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、计算机预防病毒感染有效的措施是( D )。 A.定期对计算机重新安装系统 B.不要把U盘和有病毒的U盘放在一起 C.不准往计算机中拷贝软件 D.给计算机安装防病毒的软件，并常更新 2、一个512MB的U盘能存储字节(Byte)的数据量。 A.512×8 B.512×1024×1024 C.512×1024 D.512×1024×8 3、计算机病毒是 A.计算机系统自生的 B.一种人为特制的计算机程序 C.主机发生故障时产生的 D.可传染疾病给人体的 4、在计算机内部，数据是以 A.二进制码 B.八进制码 C.十进制码

D.十六进制码 5、下面列出的四种存储器中，断电后正在处理的信息会丢失的存储器是 A.RAM B.ROM C.PROM D.EPROM 6、信息技术的四大基本技术是计算机技术、传感技术、控制技术和。 A.生物技术 B.媒体技术 C.通信技术 D.传播技术 7、内存和外存相比，其主要特点是。 A.能存储大量信息 B.能长期保存信息 C.存取速度快 D.能同时存储程序和数据 8、二十世纪末，人类开始进入 ( C )。 A. 电子时代 B. 农业时代 C. 信息时代

D. 工业时代 9、关于信息的说法，以下叙述中正确的是( D )。 A. 收音机就是一种信息 B. 一本书就是信息 C. 一张报纸就是信息 D. 报上登载的足球赛的消息是信息 10、下列不属于信息的是(C )。 A.报上登载的举办商品展销会的消息 B.电视中的计算机产品广告 C.计算机 D.各班各科成绩 11、多媒体信息不包括( D )。 A.影像、动画 B.文字、图形 C.音频、视频 D.硬盘、网卡 12、信息技术包括计算机技术、传感技术和( A.编码技术 B.电子技术 C )。 C.通信技术

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

数据结构考试题库

绪论 一、填空题 1.数据的逻辑结构被分为集合、（线性结构）、（树形结构）和（图状结构）四种。 2. 物理结构是数据结构在计算机中的表示，又称为（存储结构）。 3. 数据元素的逻辑结构包括（线性）、（树）和图状结构3 种类型，树形结构和图状结构合称为（非线性结构）。 4. （数据元素）是数据的基本单位，（数据项）是数据不可分割的最小单位。 5. 线性结构中元素之间存在（一个对一个）关系，树形结构中元素之间存在（一个对多个）关系，图状结构中元素之间存在（多个对多个）关系。 ？ 6.数据结构是一门研究非数值计算的程序设计问题中：计算机的（数据元素）以及它们之间的（关 系）和（运筹）等的学科。 7. 算法的五个重要特性为有穷性、确定性、（输入）、（输出）和（可行性）。 二、选择题 1. 数据的不可分割的基本单位是（D）。 A.元素 B.结点C数据类型D.数据项 *2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（B）。 A.正确 B.不正确C不确定 D.无法选择 3. 线性结构是指数据元素之间存在一种（D）。 A.一对多关系 B.多对多关系C多对一关系D.—对一关系

4. 在数据结构中，从逻辑上可以把数据结构分成（A）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C线性结构和非线性结构D.内部结构和外部结构 5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（D）。 A.必须是连续的 B.部分地址必须是连续的 C. 一定是不连续的 D.连续不连续都可以 三、简答题 1. 算法的特性是什么。 答：有穷性确定性可行性有0 或多个输入有 1 或多个输出 线性结构 一、填空题 1?在一个长度为n的线性表中删除第i个元素（1< i产时，需向前移动（n-i）个元素。 2. 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出元素）。 3?在线性表的单链接存储中，若一个元素所在结点的地址为p,则其后继结点的地址为（p-> next）。 4. 在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把（p->next）的值赋给q->next，然后（q->date）的值赋给p->next。 5. 从一个栈删除元素时，首先取出（栈顶元素），然后再使（栈顶指针）减1。 6. 子串的定位操作通常称做串的（模式匹配）。 7. 设目标T= ‘ abccdcdccba,模式P= ‘ cdc则第（六）次匹配成功。。 8. 顺序栈S 中，出栈操作时要执行的语句序列中有S->top（--）；进栈操作时要执行的语句序列中有S->top（++）。

《数据结构C》模拟试题

山东科技大学继续教育学院 《数据结构C》模拟试题一 班级姓名学号 一、选择题（20分） 1. 组成数据的基本单位是( )。 (A) 数据项(B)数据类型(C)数据元素(D)数据变量 2. 线性表的链接实现有利于( )运算。 (A) 插入(B)读表元(C)查找(D)定位 3. 串的逻辑结构与( )的逻辑结构不同。 (A) 线性表(B)栈(C)队列(D)树 4. 二叉树第i（i≥1）层最多有( )个结点。 (A) 2i(B)2i (C) 2i-1(D) 2i-1 5. 设单链表中p指向结点A，若要删除A后结点（若存在），则需要修改p的操作为( ) (A) p.Next = p.Next.Next (B)p=p.Next (C)p=p.Next.Next (D)p.Next=p 6. 设一数列的输入顺序为1,2,3,4,5,6，通过栈操作不可能排成的输出序列为( ) (A) 3,2,5,6,4,1 (B) 1,5,4,6,2,3 (C) 2,4,3,5,1,6 (D) 4,5,3,6,2,1 7. 设字符串S1=’ABCDEFG’，S2=’PQRST’，则运算S=CONCAT(SUB(S1,2,LENGTH(S2))，SUB(S1,LENGTH(S2),2))的结果为( ) (A) ‘BCQR’ (B) ‘BCDEF’ (C) ’BCDEFG’ (D) ‘BCDEFEF’ 8. 有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85地址为( ) (A)13 (B) 33 (C) 18 (D) 40 9. 如果结点A有3个兄弟，而且B为A的双亲，则B的度为( ) (A) 3 (B) 4 (C) 5 (D) 1 10. 线索化二叉树中某结点D没有左孩子的必要条件是( ) (A) D.Lchild=null (B) D.ltag=1 (C) D.Rchild=null (D) D.ltag=0 二、填空题（20分） 1. 对于一个以顺序实现的循环队列Q[0..m_1]，队头、队尾指针分别为f,r,其判空的条件是 ，判满的条件是。 2. 循环链表的主要优点是。 3. 给定一个整数集合{3,5,6,9,12}，画出其对应的一棵Huffman树。 4 双向循环链表中，在p所指的结点之后插入f所指的结点，其操作为。 5. 下列为朴素的模式匹配算法，请在算法的处填入正确的子句。

信息技术模拟试卷

2019年云南省中考信息技术模拟试卷(二) 一、单项选择题(15小题,每小题2分,共30分) 1.在火箭、人造卫星、宇宙飞船等尖端技术领域中,大量的数据可以快速并且准确无误地计算,这主要体现了()的实际应用。 A.通信技术 B.计算机技术 C.感测技术 D.微电子技术 2.小李下载了一个游戏,要求win7及以上系统,内存4G以上,他想查看自己电脑的配置信息是否满足游戏安装需要,要打开如下图所示的窗口,他在“计算机”右键快捷菜单中执行()命令即可。 A.管理 B.重命名 C.打开 D.属性 3.计算机中用来存放当前工作所执行的程序和数据的部件是()。 A.内存 B.CD-ROM C. CPU D.主板 4.在使用Word2010进行文档编辑时,发现录入的字符有误,此时我们按下()键来删除光标插入点右侧的字符。 A.Enter B.Space C.BackSpace D.Delete 5.在下图中显示的分栏效果是()。 A.分为两栏,有分割线 B.分为三栏,有分割线 C.分为两栏,没有分割线 D.分为三栏,没有分割线 6.在Excel中,为了让数据更直观,更好地体现数据之间的关系或者变化规律,增加数据的形象性和生动性,我们可以采用()来进行图示化呈现。

A.函数 B.图表 C.排序 D.筛选 7.如下图所示,要计算营业额,已知米线单价为5元,面条单价为6元,则D3单元格中的公式应该为()。 A.B3*5+C3*6 B.=B3*5+C3*6 C.=B3*6+C3*5 D.66*5+53*6 8.小明给小李发送了一封电子邮件,当时小李出差没有接收邮件,那么这封邮件将()。 A.退回给小明 B.自动重发 C.保存在邮件服务器上 D.丢失 9.计算机通过双绞线连接交换机就能组建最简单的计算机网络。其中,双绞线属于()。 A.网络供电设备 B.网络终端 C.网络传输介质 D.网络信息交换设备 10.在GoldWave中新建声音时,不能在新建对话框设置()。 A.声道数 B.初始化长度 C.音量 D.采样速率 11.PowerPoint2010演示文稿的扩展名是()。 A.potx B.pptx C.docx D.xlsx 12.Photoshop中,如果要将左图变成右图,应该使用()工具。 13.下列关于仿制图章工具叙述错误的是()。

数据结构考试题库含答案

数据结构习题集含答案 目录

选择题 第一章绪论 1.数据结构这门学科是针对什么问题而产生的（A ） A、针对非数值计算的程序设计问题 B、针对数值计算的程序设计问题 C、数值计算与非数值计算的问题都针对 D、两者都不针对 2.数据结构这门学科的研究内容下面选项最准确的是（D ） A、研究数据对象和数据之间的关系 B、研究数据对象 C、研究数据对象和数据的操作 D、研究数据对象、数据之间的关系和操作 3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那 么下面关于数据对象、数据元素、数据项描述正确的是（C ） A、某班级的学生成绩表是数据元素，90分是数据项 B、某班级的学生成绩表是数据对象，90分是数据元素 C、某班级的学生成绩表是数据对象，90分是数据项 D、某班级的学生成绩表是数据元素，90分是数据元素 4.*数据结构是指（A ）。 A、数据元素的组织形式 B、数据类型 C、数据存储结构 D、数据定义 5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。 A、存储结构 B、逻辑结构 C、链式存储结构 D、顺序存储结构 6.算法分析的目的是（C ） A、找出数据的合理性 B、研究算法中的输入和输出关系 C、分析算法效率以求改进 D、分析算法的易懂性和文档型性

7.算法分析的主要方法（A ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;

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

模拟试卷一 一、单选题（每题 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)，下面哪一个序列是从上述序列出发建 堆的结果?( )

2019年信息技术模拟试题一

2019年信息技术模拟试题一 1.王新在https://www.wendangku.net/doc/9215182031.html, 网站申请了用户名为wangxin2012的电子邮箱，这个E-mail地址是( ) A、wangxin2012@https://www.wendangku.net/doc/9215182031.html, B、https://www.wendangku.net/doc/9215182031.html, C、https://www.wendangku.net/doc/9215182031.html, D、wangxin2012@https://www.wendangku.net/doc/9215182031.html, 2.下列因特网的接入方式中，下行速率理论上最高的是( ) A、ADSL B、ISDN C、有线电视接入 D、光纤接入 3.Microsoft Access是一种( ) A、文字处理软件 B、幻灯片制作软件 C、数据库管理软件 D、网页制作软件 4.下列关于数据库的叙述，错误的是( ) A、同一表中不能有同名的字段 B、表中的一行称为一条记录 C、表中的一列称为一个字段 D、表与表之间不能相互关联 5.下列软件中，属于网络操作系统的是( ) A、CuteFTP B、Windows 2008 Server C、Outlook Express D、DOS 6.0 6．某单位一个大办公室内共需放置10台台式计算机，在进行网络规划时，一般考虑采用的传输介质是( ) A、单模光纤 B、双绞线 C、同轴电缆 D、多模光纤 7.下列关于JavaScript调用的叙述错误的是( ) A、嵌入在HTML页面中的JavaScript语句只能在当前页面中使用 B、多个页面用相同的JavaScript，可以将这些代码写在一个文件中 C、JavaScript语句单独保存文件，扩展名为asp D、JavaScript外部文件，使用src属性指定 8.在制作网页时，若将网页浏览器的显示空间分割为几部分，每部分可以独立显示不同的网页，且能较好地融为一体，可以使用的是( ) A、表单 B、框架 C、表格 D、层叠样式表 9.可以作为ASP编程的脚本语言是( ) A、Delphi B、VB C、VBScript D、C++ 10.在调试自己制作的网页时，发现网页标题的文字不正确。进行修改时，下列说法中正确的是( ) A、在浏览器中直接修改网页 B、用Photoshop编辑修改网页 C、用“记事本”编辑网页源代码中