安徽开放大学数据结构（本）作业与答案
安徽开放大学数据结构（本）作业与答案数据结构（本）学校:安徽开放大学平台:国家开放大学题目如下：1. 数据的存储结构包括数据元素的表示和（ ）。A. 数据处理的方法B. 数据元素间的关系的表示C. 相关算法D. 数据元素的类型答案:数据元素间的关系的表示2. 对一个栈顶指针为top的链栈进行入栈操作，通过指针变量p生成入栈结点，则执行：p=(struct node*)malloc(sizeof(struct node);p->data=a;和（ ）。A. top->next=p; p=top;B. p->next=top; top=p;C. top=top->next; p=top;D. p->next=top; p=top;答案:p->next=top; top=p;3. 树状结构中数据元素的位置之间存在（ ）的关系。A. 每一个元素都有一个直接前驱和一个直接后继B. 一对一C. 多对多D. 一对多答案:一对多4. 设头指针为head的非空的单向链表，指针p指向尾结点,则通过以下操作（ ）可使其成为单向循环链表。A. p->next = NULL ;B. head = p;C. p->next=head;D. p=head;答案:p->next=head;5. 设有一个长度为26的顺序表，要插入一个元素，并使它成为新表的第6个元素，需移动元素的个数为（）。A. 21B. 22C. 20D. 19答案:216. 一种逻辑结构（ ）。A. 只能有唯一的存储结构B. 可以有不同的存储结构C. 与存储该逻辑结构的计算机相关D. 是指某一种数据元素的性质答案:可以有不同的存储结构7. 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（ ）。A. 存储结构B. 逻辑结构C. 数据元素的存储D. 给数据元素分配存储空间答案:存储结构8. 元素111，113，115，117按顺序依次进栈，则该栈的不可能输出序列是（ ）（进栈出栈可以交替进行）。A. 117，115，113，111B. 111，113，115，117C. 117，115，111，113D. 113，111，117，115答案:117，115，111，1139. 图状结构中数据元素的位置之间存在（ ）的关系。A. 一对一B. 一对一C. 多对多D. 每一个元素都有一个且只有一个直接前驱和一个直接后继答案:多对多10. 以下说法正确的是（ ）。A. 栈的特点是先进先出B. 栈的特点是先进后出C. 队列的特点是先进后出D. 栈和队列的特点都是后进后出答案:栈的特点是先进后出11. 一个单链表中，在p所指结点之后插入一个s所指的结点时，可执行：s->next=p->next;和（ ）。A. s=p->next;B. p->next=s->next;C. p=s->next;D. p->next=s;答案:p->next=s;12. 设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵元素a6,2在一维数组B中的下标是（）。A. 21B. 28C. 17D. 23答案:1713. 数组a经初始化char a[ ]=“English”;a中存放的是（ ）。A. 字符串的结束符B. 字符hC. "h"D. 变量h答案:字符串的结束符14. 设有一个长度为32的顺序表，要删除第8个元素需移动元素的个数为（）。A. 15B. 22C. 14D. 24答案:2415. 设主串为“ABcCDABcdEFaBc”，以下模式串能与主串成功匹配的是（ ）。A. BcdB. BCdC. ABCD. Abc答案:Bcd16. 在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子的顺序编号为（ ）。A. 2i+1B. 2i-1C. 2iD. 2i+2答案:2i17. 一棵具有16个结点的完全二叉树，共有（ ）层。（设根结点在第一层）A. 7B. 6C. 4D. 5答案:518. 线性表以（ ）方式存储，能进行折半查找。A. 链接B. 顺序C. 关键字有序的顺序D. 二叉树答案:关键字有序的顺序19. 字符串“DABcdabcd321ABC”的子串是（ ）。A. “cd32”B. “ABcD”C. “aBcd”D. “321a”答案:“cd32”20. 一棵具有38个结点的完全二叉树，最后一层有（ ）个结点。A. 7B. 5C. 6D. 8答案:721. 下面关于线性表的叙述错误的是（ ）。A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用顺序存储便于插入和删除操作的实现D. 线性表采用链式存储便于插入和删除操作的实现答案:线性表采用顺序存储便于插入和删除操作的实现22. 设有头指针为head的不带头结点的非空的单向循环链表，指针p指向其尾结点，要删除第一个结点，则可利用下述语句 head=head->next;和（ ）。A. p=head;B. p=NULL;C. head=p;D. p->next =head;答案:p->next =head;23. 以下数据结构中是非线性结构的是（ ）。A. 队列B. 栈C. 二叉树D. 线性表答案:二叉树24. 以下说法正确的是（ ）。A. 线性表的链式存储结构必须占用连续的存储空间B. 一种逻辑结构可以有不同的存储结构C. 一种逻辑结构只能有唯一的存储结构D. 线性表的顺序存储结构不必占用连续的存储空间答案:一种逻辑结构可以有不同的存储结构25. 把数据存储到计算机中，并具体体现（ ）称为物理结构。A. 数据的处理方法B. 数据的性质C. 数据的运算D. 数据元素间的逻辑关系答案:数据元素间的逻辑关系26. 两个字符串相等的充要条件是（ ）。A. 两个字符串的长度相等B. 同时具备（A）和（C）两个条件C. 两个字符串中对应位置上的字符相等D. 以上答案都不对答案:同时具备（A）和（C）两个条件27. 顺序表所具备的特点之一是（ ）。A. 可以随机访问任一结点B. 不需要占用连续的存储空间C. 插入元素的操作不需要移动元素D. 删除元素的操作不需要移动元素答案:可以随机访问任一结点28. 图状结构中数据元素的位置之间存在（ ）的关系。A. 一对一B. 一对多C. 多对多D. 每一个元素都有一个直接前驱和一个直接后继答案:多对多29. 元素13，15，19，20顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）A. 20，19，15，13B. 13，15，19，20C. 19，13，15，20D. 15，13，20，19答案:19，13，15，2030. 元素20，14，16，18按顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）A. 18，16，14，20B. 20，14，16，18C. 18，16，20，14D. 14，20，18，16答案:18，16，20，1431. 设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，则在表中删除结点B的操作为（ ）。A. p->next；p=q；B. q->next=p->next；C. p->next=q->next；D. q->next=p；答案:q->next=p->next；32. 设有一个12阶的对称矩阵A（左上角第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a5,4在一维数组B中的下标是（）。A. 12B. 14C. 13D. 11答案:1433. 栈和队列的共同特点之一是（ ）。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点答案:只允许在端点处插入和删除元素34. 设有一个长度为22的顺序表，要删除第8个元素需移动元素的个数为（）。A. 25B. 14C. 15D. 23答案:1435. 用链接方式存储的队列，在进行插入运算时（ ）。A. 需修改头指针B. 头、尾指针都需要修改C. 需修改尾指针D. 头、尾指针都不需要修改答案:需修改尾指针36. 在一棵二叉树中，若编号为5的结点存在右孩子，则右孩子的顺序编号为（ ）。A. 12B. 9C. 11D. 10答案:1137. 字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（）。A. a1B. a2C. a3D. a4答案:a138. 一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。A. 14B. 15C. 19D. 18答案:1939. 设有一个20阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其 下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a6,2在一维数组B中的下标是（）。A. 23B. 17C. 21D. 18答案:1740. 字符串"abcd321ABCD"的子串是（ ）。A. "21ABC"B. "abcABCD"C. abcDD. "321a"答案:"21ABC"41. 数组a经初始化char a[ ]=“English”;a中存放的是（ ）。A. 字符EB. 字符nC. "n"D. "E"答案:字符n42. 栈和队列的共同特点是（ ）。A. 元素都可以随机进出B. 都是先进先出C. 都是先进后出D. 都是操作受限的线性结构答案:都是先进后出43. 头指针为head的带头结点的单向循环链表，p所指向尾结点，要使该链表成为不带头结点的单向循环链表，可执行head=head->nex;和（ ）。A. p= head->nextB. head->next=pC. head->next=p->nextD. p->next=head;答案:p->next=head;44. 元素12，14，16，18顺序依次进栈，则该栈的不可能输出序列是（ ）。（进栈出栈可以交替进行）。A. 18，16，14，12B. 12，14，16，18C. 14，12，18，16D. 18，16，12，14答案:18，16，12，1445. 设有串p1="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF"，以下四个串中最大的是（）。A. p3B. p2C. p1D. p4答案:p246. 设有一个30阶的对称矩阵A（第一个元素为a1,1），采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a9,2在一维数组B中的下标是（）。A. 41B. 32C. 18D. 38答案:3847. 在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（ ）。A. 2iB. 2i-1C. 2i+1D. 2i+2答案:2i+148. 如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abecdfB. aebcfdC. aecbdfD. aedfcb答案:aecbdf49. 如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abecdfgB. acfebgdC. aebcfgdD. aedfcgb答案:aedfcgb50. 如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcdfgeB. abcdfegC. acbfedgD. abcfgde答案:abcdfge51. 下图的拓扑序列是（ ）。A. 5 2 3 4 6B. 2 3 6 4 5C. 5 6 2 3 4D. 2 3 5 6 4答案:5 6 2 3 452. 设有一个长度为18的顺序表，要删除第7个元素需移动元素的个数为（ ）。A. 13B. 12C. 11D. 10答案:1153. 设某链表中最常用的操作是在链表的尾部插入或删除元素，在已知尾指针的条件下，选用下列（ ）存储方式最节省运算时间。A. 单向链表B. 单向循环链表C. 双向链表D. 双向循环链表答案:双向链表54. 如下图所示，若从顶点a出发，按图的广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcdfgeB. abcedfgC. acbfedgD. abcfgde答案:abcedfg55. 以下说法正确的是（ ）。A. 若二叉树中左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。则该树为二叉排序树。B. 二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有结点的值，则该树为二叉排序树。C. 二叉树中任意一个结点的值均大于其左孩子的值，小于其右孩子的值。则该树为二叉排序树。D. 前序遍历二叉排序树可得到一个有序序列。答案:二叉树中任意一个非叶结点的值都大于其左子树上所有结点的值，小于其右子树上所有结点的值，则该树为二叉排序树。56. 如下图所示，若从顶点6出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. 6，9，3，2，8，7，4B. 6，9，2，3，7，8，4C. 6，2，7，9，8，4，3D. 6，2，8，7，9，3，4答案:6，9，3，2，8，7，457. 如下图所示，若从顶点a出发，按图的深度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abecdfB. acfebdC. aebcfdD. aedfcb答案:aedfcb58. 如下图所示，若从顶点a出发，按广度优先搜索法进行遍历，则可能得到的一种顶点序列为（ ）。A. abcfegdB. acbfedgC. abcdfgeD. abcfgde答案:abcdfge59. 下图的拓扑序列是（ ）。A. 5 2 3 4 6B. 2 3 4 5 6C. 5 6 4 2 3D. 5 2 3 6 4答案:5 2 3 6 460. 对稀疏矩阵进行压缩存储，可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有 列。答案:1061. 结构中的数据元素存在多对多的关系称为 结构。答案:图状62. n个元素进行冒泡法排序，第j趟冒泡要进行 次元素间的比较。答案:n-j63. 中序遍历 树可得到一个有序序列。答案:二叉排序树64. 队列的操作特点是后进 。答案:后出65. 待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为 。答案:1,2,4,8,3,5,966. n个元素进行冒泡法排序，通常需要进行 趟冒泡。答案:n-167. 广义表（（a，b），d，e（（i，j），k））的长度是 。答案:468. 中序遍历二叉排序树可得到一个 的序列。答案:有序69. 广义表的（c，a，（a，b），d，e，（（i，j），k））深度是 。答案:370. 广义表（c，a，（a，b），d，e，（（i，j），k））的长度是 。答案:671. 对稀疏矩阵进行压缩存储，可采用三元组表，一个有10 行10列的稀疏矩阵A共有95个零元素，其相应的三元组表共有 个元素。答案:572. 广义表的（c，a，（a，b），d，e，（（i，j），k））深度是 。答案:373. 在对一组记录（50，49，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65 插入到有序表时，为寻找插入位置需比较次。答案:374. 一棵有5个叶结点的哈夫曼树，该树中总共有 个结点。答案:975. c语言中，字符串“E”存储时占 个字节。答案:276. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。（根所在结点为第1层）。答案:1277. 一棵二叉树中有n个非叶结点，每一个非叶结点的度数都为2，则该树共有 个叶结点。答案:n+178. 设有一个长度为40的顺序表，要删除第8个元素需移动元素的个数为 。答案:3279. 在对一组记录（55，39，97，22，16，73，65，47，88）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较次。答案:380. 有以下程序段： char a[ ]=“English”; char *p=a; int n=0; while( *p!=‘\0’){n++; p++;}结果中，n的值是 。答案:781. 设：char a[ ]="AEIJING";该字符串在计算机中存储时占 个字节。答案:882. 栈的特点之一是：元素进、出栈的次序是：先进 。答案:后出83. 结构中的数据元素存在多对多的关系称为 结构。答案:图状84. 对稀疏矩阵进行压缩存储，可采用三元组表，一个有8行的稀疏矩阵A共有92个零元素，其相应的三元组表共有4个元素。该矩阵A有 列。答案:1285. 在对10个记录的序列（9，35，19，77，2，10，53，45，27，68）进行直接插入排序时，当把第6个记录10 插入到有序表时，为寻找插入位置，元素间需比较次。（按升序排序）答案:486. 字符串a1="beijing"，a2 ="bef"，a3="beifang"，a4="befi"最小的是。答案:a287. n个元素进行冒泡法排序，第j趟冒泡要进行 次元素间的比较。答案:n-j88. 10个元素进行冒泡法排序，其中第5趟冒泡共需要进行 次元素间的比较。答案:589. 设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有 个结点。（根所在结点为第1层）答案:1290. 遍历一棵二叉排序树可得到一个有序序列。答案:中序91. 中序遍历一棵 树可得到一个有序序列。答案:二叉排序树92. 广义表（c，（a，b，c），（d，e，f），（（i，j），k））的长度是 。答案:493. 广义表的（c，（b，a，b），f，e，（（i，j），k））深度是 。答案:394. 广义表（（a，b），d，e，（（i，j），k））的长度是 。答案:495. 序列4，2，5，3，8，6，采用冒泡排序算法（升序），经一趟冒泡后，结果序列是 。答案:2,4,3,5,6,896. 广义表的（c，a，（a，b），d，e，（（i，j），k））深度是 。答案:397. 待排序的序列为8，3，4，1，2，5，9，采用直接选择排序算法，当进行了两趟选择后，结果序列为 。答案:1,2,4,8,3,5,998. 线性表用 方式存储需要占用连续的存储空间。答案:顺序99. 线性表用 方式存储可以随机访问。答案:顺序100.顺序表6，5，1，2，4，3，8，7经过一趟（1，1）归并后的结果序列为 。答案:(5,6),(1,2),(3,4),(7,8)101.以下函数为直接选择排序算法，对a，a，……，a中的记录进行直接选择排序，完成程序中的空格：typedefstruct{ int key; ……}NODE;void selsort(NODE a[ ],int n){ int i,j,k; NODE temp;for(i=1;i<= ;i++) { k=i; for(j=i+1;j<= ;j++) if(a.key答案:n-1# n# k=j# a=a# a=temp102.对线性表进行二分查找时，要求线性表必须（ ）。A. 以顺序存储方式B. 以链接存储方式C. 以顺序存储方式，且数据元素有序D. 以链接存储方式，且数据元素有序答案:以顺序存储方式，且数据元素有序103.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。A. nB. n/2C. (n+1)/2D. (n-1)/2答案:(n+1)/2104.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（ ）。A. 29/10B. 31/10C. 26/10D. 29/9答案:29/10105.已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。A. 3B. 4C. 5D. 6答案:5106.有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。A. 45,24,53,12,37,96,30B. 37,24,12,30,53,45,96C. 12,24,30,37,45,53,96D. 30,24,12,37,45,96,53答案:37,24,12,30,53,45,96107.对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。A. 3B. 6C. 4D. 5答案:4108.在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（ ）。A. 冒泡排序B. 希尔排序C. 直接选择排序D. 直接插入排序答案:直接选择排序109.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放入已排序序列的正确的位置上，此方法称为（）。A. 插入排序B. 选择排序C. 交换排序D. 归并排序答案:插入排序110.依次将每两个相邻的有序表合并成一个有序表的排序方法称为（ ）。A. 插入排序B. 交换排序C. 选择排序D. 归并排序答案:归并排序111.当两个元素出现逆序的时候就交换位置，这种排序方法称为（ ）。A. 插入排序B. 交换排序C. 选择排序D. 归并排序答案:交换排序112.每次把待排序的区间划分为左、右两个子区间，其中左区间中记录的关键字均小于等于基准记录的关键字，右区间中记录的关键字均大于等于基准记录的关键字，这种排序称为（）。A. 插入排序B. 快速排序C. 堆排序D. 归并排序答案:快速排序113.一组记录的关键字序列为（46,20,30,79，56，38，40，84,90,110），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A. 40，20,30,38，46，56，79，84,90,110B. 20,30,40，38，46，79，56，84,90,100C. 30,20,40，38，46，84，56，79,90,100D. 20,30 38，40，46，56，79，84,90,100答案:40，20,30,38，46，56，79，84,90,110114.在有序表{10,14，34，43，47，64，75，80，90}中，用折半查找法查找值80时，经（ ）次比较后查找成功。A. 4B. 2C. 3D. 5答案:3115.对序列（49，38，65，97，76，13，47，50）采用直接插入排序法进行排序，要把第七个元素47插入到已排序中，为寻找插入的合适位置需要进行（）次元素间的比较。A. 3B. 4C. 5D. 6答案:5116.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（ ）排序。A. 归并B. 插入C. 选择D. 快速答案:选择117.一组记录的关键字序列为（26，59，36，18，20，25），利用堆排序的方法建立的初始小根堆为（ ）。A. 26，18，59，20，36，25B. 18，20，25，59，26，36C. 18，20，36，59，26，25D. 26，59，36，18，20，25答案:18，20，25，59，26，36118.一组记录的关键字序列为（25，48，16，35，79，82，23，40，36，72），其中，含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（）。A. 16，25，35，48，23，40，79，82，36，72B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，82，72答案:16，25，35，48，23，40，79，82，36，72119.已知10个数据元素为（54，28，16，34，73，62，95，60，26，43），对该数列从小到大排序，经过一趟冒泡排序后的序列为（）。A. 16，28，34，54，73，62，60，26，43，95B. 28，16，34，54，62，73，60，26，43，95C. 28，16，34，54，62，60，73，26，43，95D. 16，28，34，54，62，60，73，26，43，95答案:28，16，34，54，62，73，60，26，43，95120.一组记录的关键字序列为（46，79，56，38，40，84），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。A. 40，38，46，79，56，84B. 40，38，46，56，79，84C. 40，38，46，84，56，79D. 38，40，46，56，79，84答案:40，38，46，56，79，84121.一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序（堆顶元素是最小元素）的方法建立的初始堆为（）。A. 39，46，41，57，80，47B. 39，47，46，80，41，57C. 41，39，46，47，57，80D. 39，80，46，47，41，57答案:39，46，41，57，80，47
页:
[1]