数据结构2019 作业答案

1.对线性表进行二分查找时，要求线性表必须（）。

选择一项：B. 以顺序存储方式，且数据元素有序2.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：D. (n+1)/23.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：C. 29/104.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

选择一项：C. 55.有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

选择一项：B. 37,24,12,30,53,45,966. 对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。

选择一项：A. 47.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。

选择一项：C. 直接选择排序8.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。

将其放入已排序序列的正确的位置上，此方法称为（）。

选择一项：C. 插入排序9.依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。

选择一项：C. 归并排序10.当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。

选择一项：A. 交换排序11.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。

选择一项：C. 快速排序12.一组记录的关键字序列为（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。

选择一项：B. 40，20,30,38，46，56，79，84,90,11013.在有序表{10,14，34，43，47，64，75，80，90}中，用折半查找法查找值80时，经（）次比较后查找成功。

本文部分内容来自网络整理，本司不为其真实性负责，如有异议或侵权请及时联系，本司将立即删除！== 本文为word格式，下载后可方便编辑和修改！ ==数据结构试卷篇一：数据结构试题及答案数据结构试卷（一）.................. 1 数据结构试卷（二）.................. 5 数据结构试卷（三）.................. 7 数据结构试卷（四）.................. 9 数据结构试卷（五）................. 12 数据结构试卷（六）................. 15 数据结构试卷（七）................. 17 数据结构试卷（八）................. 19 数据结构试卷（九）................. 21 数据结构试卷（十）................. 24 数据结构试卷（一）参考答案 (27)数据结构试卷（二）参考答案 ........ 28 数据结构试卷（三）参考答案 ........ 29 数据结构试卷（四）参考答案 ........ 31 数据结构试卷（五）参考答案 ........ 33 数据结构试卷（六）参考答案 ........ 34 数据结构试卷（七）参考答案 ........ 37 数据结构试卷（八）参考答案 ........ 38 数据结构试卷（九）参考答案 ........ 39 数据结构试卷（十）参考答案 .. (40)数据结构试卷（一）一、单选题（每题 2 分，共20分）1. 栈和队列的共同特点是( a )。

A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点2. 用链接方式存储的队列，在进行插入运算时( d ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3. 以下数据结构中哪一个是非线性结构？( d )A. 队列B. 栈C. 线性表D. 二叉树4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

2018最新十套数据结构试题及答案汇编2018数据结构试题（一） (1)2018数据结构试题（二） (5)2018数据结构试题（三） (8)2018数据结构试题（四） (11)2018数据结构试题（五） (15)2018数据结构试题（六） (19)2018数据结构试题（七） (22)2018数据结构试题（八） (25)2018数据结构试题（九） (28)2018数据结构试题（十） (32)2018数据结构试题（一）答案 (35)2018数据结构试题（二）答案 (37)2018数据结构试题（三）答案 (39)2018数据结构试题（四）答案 (42)2018数据结构试题（五）答案 (45)2018数据结构试题（六）答案 (47)2018数据结构试题（七）答案 (50)2018数据结构试题（八）答案 (52)2018数据结构试题（九）答案 (54)2018数据结构试题（十）答案 (56)数据结构试题（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）（1og2n） D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

0012 20191单项选择题1、用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）1. A. 选择排序2.希尔排序3.快速排序4.归并排序2、不定长文件是指（）1.记录的长度不固定2.关键字项的长度不固定3.字段的长度不固定4.文件的长度不固定3、如下陈述中正确的是（）1.串中元素只能是字母2.串是一种特殊的线性表3.串的长度必须大于零4.空串就是空白串4、将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（）1.O（m+n）2.O（n）3.O（m）4.O（1）5、设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指1. F. front=(front+1)%m2.front=(front-1)%m3.front=front+14.front=(front+1)%(m-1)6、计算机算法必须具备输入、输出和等5个特性1.易读性、稳定性和安全性2.确定性、有穷性和稳定性3.可行性、可移植性和可扩充性4.可行性、确定性和有穷性7、有8个结点的无向图最多有条边1.1122.563.284.148、不含任何结点的空树1.是一棵树2.是一棵二叉树3.是一棵树也是一棵二叉树4.既不是树也不是二叉树9、一棵深度为6的满二叉树有个分支结点1.302.313.324.3310、把一棵树转换为二叉树后，这棵二叉树的形态是1.唯一的2.有多种3.有多种，但根结点都没有左孩子4.有多种，但根结点都没有右孩子11、在对n个元素的序列进行排序时，堆排序所需要的附加存储空间是:1.O(log2n)2.O(1)3.O(n)4.O(nlog2n)12、若需要在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）1.快速排序2.堆排序3.归并排序4.直接插入13、设哈希表长m=14,哈希函数H(key)=key MOD 11。

吉大 19年11月《数据结构》作业考核试题总分：100 分一、单选题共 10 题，40 分 1 4 分带头结点的单链表 head 为空的判断条件是()。

Ahead=NULL Bhead->next=NULL Chead->next=head Dhead!=NULL 学生答案：B 2 4 分在一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p,q 之间插入s 结点，这执行（）操作。

As->next=p->next;p->next=s Bq->next=s;s->next=p Cp->next=s->next;s->next=p; Dp->next=s;s->next=q; 学生答案：B 3 4 分线性表是具有 n 个（）的有限序列 A 表元素 B 字符 C 数据元素 D 数据项学生答案：C 4 4 分在单链表中，删除p 所指结点的直接后继的操作是( ) Ap->next=p->next->next; Bp=p->next;p->next=p->next->next; Cp->next=p->next; Dp=p->next->next;学生答案：A 5 4 分任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。

A 肯定发生变化 B 有时发生变化 C 肯定不发生变化 D 无法确定学生答案：C 64 分在无向图中，所有顶点的度数之和是所有边数的( )倍。

A0.5 B1 C2 D4 学生答案：C 7 4 分单链表中，增加头结点的目的是为了( )。

A 方便运算的实现 B 用于标识单链表 C 使单链表中至少有一个结点D 用于标识起始结点的位置学生答案：A 8 4 分链栈与顺序栈相比，有一个比较明显得优点是( ) A 通常不会出现栈满的情况 B 通常不会出现栈空的情况 C 插入操作更加方便 D 删除操作更加方便学生答案：A 94 分深度为 6 的二叉树最多有( )个结点。

(单选题)1: 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。

在第一趟划分过程中，元素移动次数最多的序列是()。

A: 82，75，70，16，10，90，68，23B: 23，10，16，70，82，75，68，90C: 70，75，68，23，10，16，90，82D: 70，75，82，90，23，16，10，68正确答案:(单选题)2: 算法分析的两个主要方面是（）。

A: 空间复杂度和时间复杂度B: 正确性和简明性C: 可读性和文档性D: 数据复杂性和程序复杂性正确答案:(单选题)3: 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。

A: 10，15，14，18，20，36，40，21B: 10，15，14，18，20，40，36，21C: 10，15，14，20，18，40，36，21D: 15，10，14，18，20，36，40，21正确答案:(单选题)4: 设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。

A: 3700B: 4376C: 3900D: 4620正确答案:(单选题)5: 若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。

A: 3，2，1B: 2，1，3C: 3，1，2D: 1，3，2正确答案:(单选题)6: 下列那种排序需要的附加存储开销最大（）。

A: 快速排序B: 堆排序C: 归并排序D: 插入排序正确答案:(单选题)7: 设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。

A: O（nlog2e）B: O（n+e）C: O(n*e)D: O(n*n)正确答案:(单选题)8: 设无向图的顶点个数为n，则该图最多有（）条边。

A: n-1B: n(n-1)/2C: n(n+1)/2D: 0(单选题)9: 队列的删除操作是在（）进行。

国家开放大学2019年春季学期期末统一考试数据结构(本)试题2019年7月一、单项选择题(每小题3分，共30分)1.以下说法正确的是( )。

A.在顺序表中可以随机访问任一结点B.一种逻辑结构在存储时只能采用一种存储结构C.对链表进行插入、删除元素的操作一定要移动结点D.在链表中可以随机访问任一结点参考答案：在顺序表中可以随机访问任一结点2.线性表在存储后，如果要求：仅通过已知的指向第i个结点的指针，进行相关操作，访问到该结点的前驱结点，则采用( )存储方式是不可行的。

A.单链表B.双链表C.单循环链表D.顺序表参考答案：单链表3.栈和队列的共同特点是( )。

A.都是先进后出B.元素都可以随机进出C.只容许在端点处插人和删除元素D.都是先进先出参考答案：只容许在端点处插人和删除元素4.元素4，6，8，10按顺序依次进栈，按该栈的可能输出序列依次人队列，该队列的可能输出序列是( )(进栈出栈可以交替进行)。

A.10，8，4，6 C.8，4，6，10B.10，6，4，8 D.10，8，6，4参考答案：10，8，6，45.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，从该队列中进行出队操作，并把结点的值保存在变量x中的操作为( )。

A.x=r->data；r=r->next；B.r一r一>next；x=r一>data；C.x=f~>data；f=f->next；D.f一f->next；x-f一>data；参考答案：x=f~>data；f=f->next；6.设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存到一维数组B中(数组下标从1开始)，则矩阵元素ag.2对应于数组B 中第( )号元素。

(矩阵中的第1个元素是a1.1)A.42B.39C.38D.40参考答案：387.一棵采用链式存储的二叉树中，共有n一1个指针域被有效使用(即指针域为非空)。

1．第1题下列各式中，按增长率由小至大的顺序正确排列的是( )。

A．n1/2，n!，2n，n3/2B．n3/2，2n，n logn，2100C．2n，logn，n logn，n3/2D．2100，logn, 2n, n nA.AB.BC.CD.D您的答案：D题目分数：2此题得分：2.02．第2题串s=″Data Structure″中长度为3的子串的数目是( )。

A.9B.11C.12D.14您的答案：C题目分数：2此题得分：2.03．第5题给定整数集合{3,5,6,9,12}，与之对应的哈夫曼树是( )。

A.AB.BC.CD.D您的答案：C题目分数：2此题得分：2.04．第6题连通网的最小生成树是其所有生成树中( )。

A.顶点集最小的生成树B.边集最小的生成树C.顶点权值之和最小的生成树D.边的权值之和最小的生成树您的答案：D题目分数：2此题得分：2.05．第7题如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( )。

A.有向完全图B.连通图C.强连通图D.有向无环图您的答案：D题目分数：2此题得分：2.06．第18题以下广义表关系正确的是( )。

A.线性表<再入表<纯表<递归表B.线性表<纯表<递归表<再入表C.纯表<线性表<再入表<递归表D.线性表<纯表<再入表<递归表您的答案：D题目分数：2此题得分：2.07．第19题假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。

A.k-1B.kC.k+1D.k(k+1)/2您的答案：D题目分数：2此题得分：2.08．第20题n个记录直接选择排序时所需的记录最多交换次数是( )。

A.n-1B.nC.n(n-1)/2D.n(n+1)/2您的答案：A题目分数：2此题得分：2.09．第21题线索二叉树中某结点为叶子的条件是( )。

A.p-> lchild!=NULL || p-> rchild!=NULLB.p-> ltag==0 || p-> rtag==0C.p-> lchild!=NULL & & p-> rchild!=NULLD.p-> ltag==1 & & p-> rtag==1您的答案：D题目分数：2此题得分：2.010．第22题设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为( )。

题号题目内容答案答题时间1"空串与空格串是相同的，这种说法____。

A.正确B.不正确"B02"串是一中特殊的线性表，其特殊性体现在____。

A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符"B03"设有两个串p和q，求q在p中首次出现的位置的运算称作____。

A.连接B.模式匹配C.求子串D.求串长"B04"设串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))的结果串是____。

A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF"D05"常对数组进行的两种基本操作是____。

A.建立与删除B.索引和修改C.对数据元素的存取和修改D.查找与索引"C06"二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要①_ _个字节；M 数组的第8列和第5行共占②____个字节。

A.90B.180C.240D.540E.108F.114G.54H.60"DE07"二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是____。

A.80B.100C.240D.270"C08"由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____。

A.正确B.错误"B09"假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。