电大《数据结构与算法》形考题库

1.请用循环队列编写程序求解素数环问题。

【实验目的】练习循环队列的使用，包括循环队列如何插入数据元素、删除数据元素等。

【实验要求】将1~n的自然数排列成环形，使得相邻两数之和为素数，构成一个素数环。

【实验分析】任意两数和为素数，可以从1开始找，对2~n进行测试，如果它与环中最后那个数的和为素数，则将其加入环中；否则暂时放回，待下次进行判断。

【实验步骤】素数环可以用循环队列实现，存放2~n的数可以用另一个队列。

Step1：建立空的素数环队列A，插入1。

Step2：建立存放待排数的队列B，依次插入2~n。

Step3：从队列B中取队头，计算与队列A队尾之和，如和为素数，则插入队列A；否则将取下的该队头插入队列B队尾。

Step4：继续重复Step3，直至队列B空。

2.请用栈实现数值转换（十进制转换为八进制）。

【实验目的】练习栈的使用，包括栈的入栈、出栈、取栈顶等操作。

【实验要求】利用一个顺序栈、除法运算及模运算将十进制数N转换为八进制数。

【实验分析】其转换方法利用辗转相除法（N/r），每次将除法结果放入N中，将得到的余数依次放入栈中，当除法结果为0时，依次出栈所有数据，即得到转换后的数据。

【实验步骤】当N>0时，重复Step1，Step2。

Step1：若 N≠0，则将N % r压入栈s中，执行Step2； 若N=0，则将栈s的内容依次出栈，算法结束。

Step2：用N / r代替 N。

1.实现冒泡排序算法

【实验目的】熟悉并练习冒泡排序算法过程。

【实验要求】一组无序数据序列存储在数组中，对其进行冒泡排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。

【实验分析】冒泡排序是不停地比较相邻的记录，如果不满足排序要求（逆序），就交换相邻记录，经过从尾到头（或从头到尾）的一趟扫描后，最小（或最大）的元素就排到了最前面（或最后面）。

2.实现直接插入排序算法

【实验目的】熟悉并练习直接插入排序算法过程。

【实验要求】一组无序数据序列存储在数组中，对其进行直接插入排序后得到有序数据序列。要求空间复杂度要尽可能低，即尽量少用额外辅助空间。

【实验分析】直接插入排序是将一个待排序的记录按其关键字的大小插入一个已经排好序的有序序列中合适的位置，在开始时，把第一个记录看成已经排好序的初始有序序列；寻找待插入记录的位置需要进行元素关键字的比较，当比较到比前面关键字大，比后面关键字小的位置，则插入该记录。

题目1：下面说法错误的是（）。

A. 数据结构是指互相之间存在着一种或多种关系的数据元素的集合

B. 数据（Data）是指客观事物的符号表示

C. 数据元素是表示数据的不可分割的最小标识单位

D. 数据的基本单位是数据元素

题目2：数据结构中的线性结构是指（）。

A. 数据元素之间属于同一个集合

B. 数据元素之间存在着一对一的线性关系

C. 数据元素之间存在着一对多的线性关系

D. 数据元素之间存在着多对多的线性关系

题目3：下列有关递归的说法错误的是（）。

A. 递归需要有边界条件、递归方程两部分构成。

B. 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算。

C. 递归通常把一个复杂问题层层转化为一个与原问题相似的规模较小的问题来求解。

D. 只有在函数中直接调用自身才能叫做递归函数。

题目4：根据数据元素之间关系的不同，数据结构分为（）。

A. 物理结构，逻辑结构

B. 集合结构，线性结构，树结构，图结构

C. 顺序结构，链表结构

D. 递归结构，普通结构

题目5：栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈，下列（）序列是可能的出栈序列。

A. E、D、C、B、A、F

B. B、C、E、F、A、D

C. B、D、C、F、E、A

D. A、D、F、E、B、C

题目6：顺序循环队列容量为50，队头表示第一个元素的位置，队尾表示最后一个元素的下一个位置，当队头为31，队尾为8的时候，队列中共有（）个元素。

A. 25

B. 26

C. 27

D. 28

题目7：对线性表，在下列（）情况下应当采用链表表示。

A. 经常需要随机地存取元素

B. 经常需要进行插入和删除操作

C. 表中元素需要占据一片连续的存储空间

D. 表中元素的个数不变

题目8：若用一个大小为8的数组来实现循环队列，且当tail和head的值分别为6，0。当从队列中删除两个元素，再加入一个元素后，tail和head的值分别为（）。

A. 6和5

B. 7和2

C. 2和7

D. 5和6

题目9：设循环队列的元素存放在一维数组Q[50]中，head指向队头元素，tail指向队尾元素的后一个位置。若head=27，tail=6，则该队列中的元素个数为（）。

A. 19

B. 20

C. 29

D. 40

题目10：下列有关队列及其应用叙述错误的是（）。

A. 队列是操作受限制的线性表

B. 队列的入队顺序和出队顺序是一致的

C. 解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区是一个队列结构

D. 设计一个判别表达式中左右括号是否配对的算法，采用队列数据结构最佳

题目11：一个栈的输入序列为1 2 3 4，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 1 4

B. 3 2 4 1

C. 1 2 3 4

D. 3 1 2 4

题目12：用链接方式存储的非空队列，队列长度为6，在该链队列中删除一个元素时（）。

A. 仅修改队头指针

B. 队头、队尾指针都要修改

C. 仅修改队尾指针

D. 队头、队尾指针都不需修改

题目13：下列有关队列及其应用叙述正确的是（）。

A. 队列中每一个元素都有唯一的直接前驱和唯一的直接后继

B. 队列的插入在队头进行

C. 队列的删除在队尾进行

D. 队列中的队头元素有唯一的直接后继

题目14：设有字符串p，返回字符在字符串中第一次出现的位置称作（）。

A. 查找

B. 求子串

C. 求串长

D. 连接

题目15：串S1=“ab123”，S2=“ab45”，则S1 （） S2。

A. >；

B. <；

C. =

D. 不确定

题目16：广义表G=（a，G）的长度为（）。

A. 1

B. 2

C. 3

D. 无穷大

题目17：树的度是指（）。

A. 树中某个结点拥有的子树棵数

B. 树中所有结点度的和

C. 树中所有结点度的最大值

D. 树中所有结点度的最小值

题目18：如果二叉树根结点的层次为1，二叉树共4层，则整棵二叉树最多有（）个结点。

A. 15

B. 16

C. 17

D. 18

题目19：二叉树如图所示，其先序遍历结果为（）。

A. （BDEFHMPRTWZ）

B. （HDBFERMPWTZ）

C. （BEFDRMPWTZH）

D. （BEFDPMTZWRH）

题目20：为4个使用频率不等的字符设计哈夫曼（Huffman）编码，不可能的方案是（）。

A. 110，10，01，00

B. 000，001，010，01

C. 001，010，000，011

D. 001，01，11，10

题目21：算法的设计取决于所选定的存储结构。

A. 对

B. 错

题目22：数据结构中的树结构是指数据元素之间存在着一对一的线性关系。

A. 对

B. 错

题目23：顺序表会开辟连续的存储空间存储数据。

A. 对

B. 错

题目24：栈只能在栈底端进行插入删除。

A. 对

B. 错

题目25：在顺序栈中，TOP始终指向栈底的位置，就是放置新元素的位置。

A. 对

B. 错

题目26：字符串是一种操作受限的线性表。

A. 对

B. 错

题目27：单字符链表每个结点只存储一个字符。

A. 对

B. 错

题目28： 广义表可以被其他广义表共享。

A. 对

B. 错

题目29： 由中序序列和后序序列可以构造出一棵唯一的二叉树。

A. 对

B. 错

题目30：哈夫曼树中结点的度可以是0，1，2。

A. 对

B. 错

题目1：无向图的顶点个数为n，则图中边数的最大值为（）。

A. n× （n-1）

B. n× （n-1）/2

C. n-1

D. n

题目2：在一个无向图中，所有顶点的度数之和等于所有边数的（）。

A. 3倍

B. 2倍

C. 1倍

D. 0.5倍

题目3：在图的邻接矩阵存储结构中删除一个顶点，下列说法错误的是（）。

A. 直接在删除顶点处做删除标记即可

B. 删除顶点顺序表中的该顶点

C. 删除邻接矩阵中该顶点所在的行

D. 删除邻接矩阵中该顶点所在的列

题目4：一个有e条边的无向图，邻接表中包含的边结点的总数是（）。

A. e

B. e-1

C. e+1

D. 2e

题目5：对于下图的无向图，插入一个顶点E后，顶点顺序表为（）。

A. 选项A

B. 选项B

C. 选项C

D. 选项D

题目6：对于下面的图，从结点0开始进行深度优先搜索，可能的搜索结果是（）。

A. 0，1，2，3，4，5

B. 0，1，2，3，5，4

C. 0，2，3，4，1，5

D. 0，4，3，1，2，5

题目7：对于下面的图，从结点1开始进行广度优先搜索，可能的搜索结果是（）。

A. 1，3，2，4，0，5

B. 1，0，4，2，3，5

C. 1，3，0，2，4，5

D. 1，5，0，2，4，3

题目8：设一组初始记录关键字序列为（17，29，32，48，51，63，78，92，151），则利用顺序查找方法查找关键字78需要比较的关键字个数为（）。

A. 5

B. 6

C. 7

D. 8

题目9：设一组初始记录关键字序列为（12，25，27，37，52，61，72，89，97），则利用折半查找过程中第一个比较的关键字是（）。

A. 12

B. 17

C. 52

D. 61

题目10：设一组初始记录关键字序列为（28，32，49，53，67，71，86，94，115，128，136），则利用折半查找关键字128需要比较的关键字个数为（）。

A. 1

B. 2

C. 3

D. 4

题目11：按{12，24，36，90，52，30}的顺序构成的二叉排序树，其叶子结点是（）。

A. 30，52

B. 24，36

C. 52，90

D. 12，24

题目12：将{12，24，36，90，52，30}6个元素构成平衡二叉排序树，其根结点是（）。

A. 12

B. 24

C. 52

D. 36

题目13：对于折半查找法，一般选择（）作为其存储结构。

A. 顺序表

B. 循环表

C. 双链表

D. 单链表

题目14：基本有序的序列适合用（）排序算法进行排序。

A. 归并

B. 直接插入

C. 快速

D. 堆

题目15：直接插入排序的时间复杂度是（）。

A. O（n2）

B. O（n）

C. O（nlog2n）

D. O（1）

题目16：对序列{82 61 43 77}进行从头到尾的冒泡排序，第一趟扫描排序结果为（）。

A. 61 82 43 77

B. 61 43 77 82

C. 61 43 82 77

D. 43 61 77 82

题目17：判别下列序列中，不是堆的是（）。

A. （3，7，17，25，36，47，85，29，52）

B. （82，57，63，41，35，48，52，21，30）

C. （5，8，10，12，30，9，17，36，45）

D. （95，43，65，23，38，57，80，15，17 ）

题目18：对序列{45 53 58 36 72 30 48 93}进行归并排序，第二趟两两归并结果为（）。

A. （36 45 53 58） （30 48 72 93）

B. （45 53 58 36）（72 30 48 93）

C. （45 53）（36 58）（30 72）（48 93）

D. （30 36 45 48 53 58 72 93）

题目19：下列关于回溯法的描述错误的是（）。

A. 回溯法按照规则去试探

B. 回溯法就是是穷举式搜索

C. 回溯法中候选解满足问题的所有要求，该候选解就是问题的一个解

D. 回溯是指放弃当前的候选解，退到上一步

题目20：将大问题化为相互独立的相同的小问题，然后各个击破，解决完小问题后再合成大问题的解是（）算法的算法思想。

A. 动态规划算法

B. 分治法

C. 回溯算法

D. 贪心算法

题目21：有n个顶点的有向完全图，有n（n-1）条边。

A. 对

B. 错

题目22：有向图的邻接矩阵一定是不对称的。

A. 对

B. 错

题目23：邻接表只适于无向图的存储，不适合有向图的存储。

A. 对

B. 错

题目24：一个图可以有多个生成树。

A. 对

B. 错

题目25：n个顶点的连通图G的生成树含有n-1条边。

A. 对

B. 错

题目26：如果表中不存在想要查找的关键字，则查找失败。

A. 对

B. 错

题目27：如果二叉排序树的左子树不空，则左子树上结点的值均大于根结点的值。

A. 对

B. 错

题目28：对于最小堆来说，堆顶结点具有最大值。

A. 对

B. 错

题目29：当待排序的记录数目n较小时，适合采用直接插入法进行排序。

A. 对

B. 错

题目30：N后问题最常用回溯法解决。

A. 对

B. 错