郑大远程数据结构习题

第一章第一题、单项选择题（每题1分，5道题共5分）1、在计算机中,数据的基本单位是BA、数据B、数据元素C、数据项D、数据构造2、网状数据构造中数据元素之间的对应关系是CA、1:1B、1:NC、M:ND、N:13、一个算法的实现取决于选定的BA、逻辑构造B、储藏构造C、时间复杂度D、空间复杂度4、在数据构造的谈论中,可把数据构造从逻辑上分为DA、静态构造与动向构造B、内部构造与外面构造C、紧凑构造与非紧凑构造D、线性构造与非线性构造5、算法的效率一般用什么来胸襟AA、时间复杂度B、空间复杂度C、执行的时间D、占用的空间第二题、多项选择题（每题2分，5道题共10分）1、数据构造一般有以下几各种类ABCDA、会集B、线性构造C、树形构造D、图形构造2、算法的重要特点有ABCDA、有穷性B、确定性C、可行性D、有输出3、以下哪写是数据构造的基本操作ABCDA、插入B、删除C、查找D、更正4、关于C语言而言,以下哪些是基本数据种类ABCDA、整型B、实型C、字符型D、布尔型E、构造体种类5、非线性构造主若是指ACDA、会集B、表C、树形构造D、图形构造第三题、判断题（每题1分，5道题共5分）1、数据是信息的载体,是对客观事物的符号表示对正确错误2、数据构造是相互之间存在一种或多种特定关系的数据元素的会集对正确错误3、储藏构造是数据构造在计算机中的表示,也称为数据的物理构造.对正确错误4、树形构造中的数据元素之间存在一个对一个的关系错正确错误5、图形构造中的元素存在多个对多个的关系.对正确错误第二章第一题、单项选择题（每题1分，5道题共5分）1、关于一个长度为

n的次序储藏的线性表，在表尾插入元素的时间复杂度为

CA、O(n)

B、O(n*n)C、O(1)

D、O(0)2、在一个长度为

n的次序储藏的线性表中，删除第

i个元素（

1≤i≤n）时，需要从前向后依次前移几个元素。

AA、n-i

B、n-i+1C、n-i-1

D、i3、采用链式构造表示一个线性表时

,要求占用的储藏空间地址

DA、必定是连续的

B、部分地址必定是连续的C、必然是不连续的

D、可连续可不连续4、设次序表第一个元素X的储藏地址A、loc(X)+(I-1)*l,其中l为每个元素的大小C、loc(X)+(I+1)*l,其中l为每个元素的大小

loc(X)为基地址,则第I个元素Y的储藏地址为B、loc(X)+I*l,其中l为每个元素的大小D、(I-1)*l,其中l为每个元素的大小

A5、单链表插入操作的平均时间复杂度为

BA、O(1)

B、O(n)C、O(n*n)

D、O(n*n*n)第二题、多项选择题（每题2分，5道题共10分）1、在次序表中删除一个元素的步骤主要有没找到正确答案A、检查线性表可否为空B、检查删除地址可否合法C、使表长减1D、删除成功,返回一个表示成功的值2、次序表的特点有ABCDA、储藏构造简单B、易于实现C、节约空间D、可随机储藏3、单链表的节点一般应包括ABA、数据域B、指针域C、节点域D、储藏域4、线性表用链式构造来实现,可有哪些形式ABCDA、单链表B、双链表C、循环链表D、双向循环链表5、以下哪些是线性表的常用操作ABCDA、插入B、删除C、查找D、判断可否为空第三题、判断题（每题1分，5道题共5分）1、关于线性表L,当元素个数为0时,一般称为空表对正确错误2、在线性表中插入一个元素后,线性表的长度比插入前增加1对正确错误3、线性表就是指次序表错正确错误4、在线性链表中插入一个元素是不会出现无法插入的情况的错正确错误5、单链表中的各个元素若是不储藏在连续的空间内,那么从实质上来看它就不是线性构造错正确错误第三章第一题、单项选择题（每题1分，5道题共5分）1、在队列中,赞同删除元素的一端称为AA、队首B、队尾C、入队D、出队2、一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈不能能的输出序列是CA、a5,a4,a3,a2,a1B、a4,a5,a3,a2,a1C、a4,a3,a5,a1,a2D、a1,a2,a3,a4,a53、在一个链队列中，假设f和r分别为队首和队尾指针，删除一个结点的运算是CA、r＝f-＞nextB、r＝r-＞nextC、f＝f-＞nextD、f＝r-＞next4、在一个拥有n个单元的次序栈中，假设栈底是储藏地址的低端，现在我们以top作为栈顶指针，则作退栈操作时，top的变化是AA、top＝top-1;B、top＝top+1;C、top不变D、top不确定5、假溢出现象只会出现在哪一种数据构造中DA、次序表B、链表C、栈D、队列第二题、多项选择题（每题2分，5道题共10分）1、栈的常用操作有ABCDA、入栈B、出栈C、取栈顶元素D、清空栈2、栈的实现方式主要有ABA、次序方式B、链式方式C、循环方式D、递归方式3、一个栈的入栈序列为a1,a2,a3,a4,a5,则此栈可能的输出序列是ABA、a1,a2,a3,a4,a5B、a5,a4,a3,a2,a1C、a1,a5,a3,a4,a2D、a5,a1,a2,a3,a44、队列的常用操作有ABCA、入队B、出队C、取队首元素D、取队尾元素5、队列的实现方式主要有ABA、次序方式B、链式方式C、循环方式D、递归方式第三题、判断题（每题1分，5道题共5分）1、向栈顶插入一个元素的操作叫入栈对正确错误2、由于次序栈占用连续的储藏空间,因此能够随机存取栈中的元素错正确错误3、由于队列元素的操作拥有"先进先出"的特点,因此队列又称为先进先出表对正确错误4、在队列中赞同删除的一端称为队首对正确错误5、队列只能用次序方式来实现错正确错误第四章第一题、单项选择题（每题1分，5道题共5分）1、设串s1＝"ABCDEFG",s2＝"PQRST",函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的字符，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是

DA、BCDEFC、BCPQRST

B、BCDEFGD、BCDEFEF2、空格串的长度为

DA、0

B、1C、大于1

D、大于等于

13、设s1＝"GOOD"，s2＝"-",s3＝"BYE！"，则

s1、s2和s3连接后的结果是

AA、"GOOD-BYE！"

B、"GOODBYE！"C、"GOODBYE！"

D、"GOODBYE"4、数组

A中，每个元素

A的长度为

3个字节，行下标

i从1到8，列下标

j从1到10

，从首地址

SA开始连续存放在储藏器内，该数组按行存放时，元素

A[8][5]的起使地址为

CA、SA+141

B、SA+180C、SA+222

D、SA+2255、稀罕矩阵一般的压缩储藏方法有两种，即CA、二维数组和三维数组B、三元组和散列C、三元组和十字链表D、散列和十字链表第二题、多项选择题（每题2分，5道题共10分）1、在一般的程序设计语言中,串中的元素能够是ABCDA、字母B、阿拉伯数字C、一些特别符号D、汉字2、以下说法正确的选项是ABCDA、数组也是一种线性数据构造B、一维数组从实质上看就是线性表C、二维数组是数据元素为一维数组的线性表D、数组是由值与下标组成的数偶的有序会集3、常有的特别矩阵有ABCA、对称矩阵B、三角矩阵C、对角矩阵D、二维矩阵4、稀罕矩阵的储藏方法一般有ABA、三元组表法B、十字链表法C、循环链表法D、堆方法5、串的基本操作包括ABCDEA、连接B、求串长C、串比较D、子串定位E、串复制第三题、判断题（每题1分，5道题共5分）1、长度为零的串称为空串对正确错误2、串中任意个连续的字符组成的子序列称为该串的子串对正确错误3、串既能够用次序方式表示,也能够用链式方式表示对正确错误4、数组的储藏构造一般都采用次序储藏构造对正确错误5、C语言中,数组的实现采用列优先的储藏方式错正确错误第五章第一题、单项选择题（每题1分，5道题共5分）1、在一棵二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0＝BA、n2B、n2+1C、n2-1D、n2+22、现有按中序遍历二叉树的结果为abc，问有几种不相同形态的二叉树能够获取这一遍历结果DA、2B、3C、4D、53、带权路经长度最小的树称为CA、满二叉树B、完好二叉树C、哈夫曼树D、线索二叉树4、若用10,6,20,23,8,1,5做为权值,构造一棵哈夫曼树,该树的深度为BA、4B、5C、6D、75、将一棵树变换为一个二叉树后,该二叉树必然BA、没有左子树B、没有右子树C、所有的节点都没有左子树D、所有的节点都没有右子树第二题、多项选择题（每题2分，5道题共10分）1、二叉树的遍历方法有ABCDA、前序法B、中序法C、后序法D、层次遍历法2、树的逻辑构造表示法有ABCDA、树形表示法B、文氏图表示法C、凹入表示法D、括号表示法3、二叉树的基本操作主要有

ABCDA、遍历B、求二叉树的深度C、求某个节点的左子女D、求某个节点的左子女4、二叉树的实现方法主要有

ABA、次序方式B、链式方式C、循环方式D、递归方式5、树的实现方式主要有

ABA、次序方式B、链式方式C、循环方式D、递归方式第三题、判断题（每题

1分，5道题共5分）1、由树变换成二叉树，其根结点的右子树总是空的

对正确

错误2、后根遍历树和中序遍历与该树对应的二叉树，其结果不相同

错正确

错误3、后序遍历森林和中序遍历与该森林对应的二叉树，其结果不相同

错正确

错误4、用二叉树的前序遍历和中序遍历能够导出二叉树的后序遍历

对正确

错误5、在二叉树中，拥有一个子女的父结点，在中序遍历序列中，它没有后继子女结点正确错误

错第六章第一题、单项选择题（每题

1分，5道题共5分）1、拥有6个极点的无向图最少应有＿＿＿条边才能保证是一个连通图

AA、5

B、6C、7

D、82、关于一个拥有

n个极点的无向图，若采用毗邻矩阵表示，则该矩阵的大小是＿＿＿

DA、n

B、(n-1)*(n-1)C、n-1

D、n*n3、采用毗邻表储藏的图的深度优先遍历算法近似于二叉树的

AA、先序遍历

B、中序遍历C、后序遍历

D、按层遍历4、要点路径是事件结点网络中AA、从源点到汇点的最长路径B、从源点到汇点的最短路径C、最长的回路

D、最短的回路5、一个图中包括有

k个连通重量，若按深度优先找寻的方法接见所有结点，则必定调用＿＿＿＿次深度优先算法

AA、k

B、1C、k-1

D、k+1第二题、多项选择题（每题

2分，5道题共10分）1、完好图包括

ABA、无向完好图B、有向完好图C、连通图D、完好连通图2、图的常用储藏方法有

BCA、散列方法B、毗邻矩阵法C、毗邻表法D、次序方法3、图的遍历方法有

ABA、深度优先方法B、广度优先方法C、先根方法D、后根方法4、拓扑排序的主要步骤有

ABCA、在AOV网中,选一个没有后继的节点,并输出B、在网中删去该极点,并删去所有指向该极点的弧C、重复上述两步,直到网中不再有出度为0的极点为止D、删除网中的回路5、常用的最小生成树算法有ABA、普里姆算法B、克鲁斯卡尔算法C、哈夫曼算法D、拓扑算法第三题、判断题（每题1分，5道题共5分）1、在N个结点的无向图中，若边数大于N-1，则该图必是连通图错正确错误2、任何AOV网的拓扑序列都是唯一的错正确错误3、毗邻表只能用于储藏有向图，而毗邻矩阵则可储藏有向图和无向图错正确错误4、无向图的毗邻矩阵是对称的，因此可只储藏毗邻矩阵的下（或上）三角阵对正确错误5、强连通重量是有向图中的极大强连通子图对正确错误第七章AADAB对错对对错第一题、单项选择题（每题

1分，5道题共5分）1、若是要求一个线性表既能较快地查找，又能适应动向变化的要求，能够采用＿＿＿查找方法A、分块B、次序C、二分D、散列

A2、一个有序次序表有

255个元素，采用次序查找法查找，查找长度为

AA、128

B、127C、126

D、2553、在散列函数

H（key）＝key％p中，p一般取

DA、大于1000的数

B、小于1000的数C、随机数

D、素数4、关于二叉排序树的查找，若根结点元素的键值大于被查找元素的键值，则应该在二叉树的＿＿＿上连续查找AA、左子树

B、右子树C、左右两棵子树

D、根接点5、在一棵二叉排序树上推行＿＿＿＿＿＿＿遍历后，其要点字序列是一个有序表

BA、先序

B、中序C、后序

D、深度第二题、多项选择题（每题

2分，5道题共10分）1、依照对查找表中的数据所执行的操作,可将查找表分为ABA、静态查找表B、动向查找表C、树表D、链表2、以下哪些是哈希函数的构造方法ABCDA、直接地址法B、除留余数法C、平方取中法D、折叠法3、下面哪些是办理矛盾的方法ABA、开发地址法B、链地址法C、索引法D、二分法4、哈希表的缺点主要有ABCA、依照哈希函数计算要点字的地址的过程占用必然的计算时间B、占用的储藏空间多C、在哈希表中只能按要点字查找D、不能够进行删除操作5、开发地址法可进一步分为ABA、线性探测法B、二次探测法C、随机探测法D、链地址法第三题、判断题（每题1分，5道题共5分）1、哈希表的查找效率主要取决于哈希表成马上采用的哈希函数和办理矛盾的方法对正确错误2、直接定址法构造的哈希函数会发生矛盾错正确错误3、折半查找是一种在有序表进步行查找的方法对正确错误4、由二叉排序树的定义可知,中序遍历二叉树所获取的序列是非递减有序的对正确错误5、从哈希表中删除一个数据元素时是不需要使用哈希函数的错正确错误第八章第一题、单项选择题（每题

1分，5道题共5分）1、一组记录的排序码为{46，79，56，38，40，84}，则利用堆排序的方法建立的初始堆为A、79，46，56，38，40，84B、84,79，56，38，40，46C、84,79，56，46，40，38D、84，56，79，40，46，38

B2、排序方法中，从未排序序列中优选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为DA、希尔排序B、归并排序C、插入排序D、选择排序3、一组记录的排序码为{25，48，16，35，79，82，23，40，36，72}，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一次归并后的结果为AA、16253548234079823672B、16253548798223364072C、16254835798223364072D、162535487