发布时间 : 星期一 文章计算机软件技术基础试题库更新完毕开始阅读0709dc597e192279168884868762caaedd33bac2
A) 希尔排序 B) 冒泡排序 C) 插入排序 D) 选择排序
(82) 从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为
（ ）。
A) 希尔排序 B) 归并排序 C) 插入排序 D) 选择排序 (83) 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（ ）
A) 从小到大排列好的 C) 元素无序
B) 从大到小排列好的 D) 元素基本有序
(84) 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（ ）。
A) n+1 B) n
C) n-1 D) n(n-1)/2
(85) 快速排序在下列哪种情况下最易发挥其长处。（ ）
A) 被排序的数据中含有多个相同排序码 B) 被排序的数据已基本有序 C) 被排序的数据完全无序
D) 被排序的数据中的最大值和最小值相差悬殊
(86) 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（ ）。
A) O(n)
B) O(n2)
C) O(nlog2n)
D) O(n3)
(87) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基
准得到的一次划分结果为（ ）。
A) 38, 40, 46, 56, 79, 84 B) 40, 38, 46 , 79, 56, 84 C) 40, 38，46, 56, 79, 84 D) 40, 38, 46, 84, 56, 79 (88) 下列关键字序列中，（ ）是堆。
A) 16, 72, 31, 23, 94, 53 C) 16, 53, 23, 94，31, 72 (89) 堆是一种（ ）排序。
A) 插入 B) 选择 (90) 堆的形状是一棵（ ）。
A) 二叉排序树 B) 满二叉树
C) 完全二叉树 D) 平衡二叉树 C) 交换
D) 归并
B) 94, 23, 31, 72, 16, 53 D) 16, 23, 53, 31, 94, 72
(91) 若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为（ ）。
A) 79, 46, 56, 38, 40, 84 C) 84, 79, 56, 46, 40, 38
B) 84, 79, 56, 38, 40, 46 D) 84, 56, 79, 40, 46, 38
(92) 下述几种排序方法中，要求内存最大的是（ ）。
A) 插入排序 B) 快速排序 C) 归并排序 D) 选择排序
(93) 有一组数据（15，9，7，8，20，-1，7，4），用堆排序的筛选方法建立的初始堆为（ ）。
A) -1，4，8，9，20，7，15，7
B) -1，7，15，7，4，8，20，9
C) -1，4，7，8，20，15，7，9 D) A，B，C 均不对。
(94) 51．下列四个序列中，哪一个是堆（ ）。
A) 75,65,30,15,25,45,20,10 C) 75,45,65,30,15,25,20,10 (95) 以下序列不是堆的是( )。
A) (100,85,98,77,80,60,82,40,20,10,66) C) (10,20,40,60,66,77,80,82,85,98,100)
B) (100,98,85,82,80,77,66,60,40,20,10) D) (100,85,40,77,80,60,66,98,82,10,20)
B) 75,65,45,10,30,25,20,15 D) 75,45,65,10,25,30,20,15
(96) 快速排序方法在（ ）情况下最不利于发挥其长处。
A) 要排序的数据量太大
B) 要排序的数据中含有多个相同值 D) 要排序的数据已基本有序
C) 要排序的数据个数为奇数
(97) 对关键码序列28，16，32，12，60，2，5，72 快速排序，从小到大一次划分结果为（ ）。
A) (2,5,12,16)26(60,32,72) C) (2,16,12,5)28(60,32,72)
B) (5,16,2,12)28(60,32,72) D) (5,16,2,12)28(32,60,72)
(98) 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ ）。
A) {21,25,5,17,9,23,30} C) {21,9,17,30,25,23,5} 二、填空题
(99) 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
(100) 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系 有限集合。
(101) 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
(102) 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 (103) 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
(104) 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有 后续结点，其余每个结点有且只有1个后续结点。
(105) 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
(106) 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
(107) 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
(108) 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
B){25,23,30,17,21,5,9} D) {5,9,17,21,23,25,30}
(109) 一个算法的效率可分为 时间 效率和 空间 效率。
(110) 对于给定的n个元素,可以构造出的逻辑结构有 集合，线性表，树，图四种。 (111) 顺序映象的特点是借助元素在存储器中的 相对位置来表示数据元素之间的逻辑关系。非顺序映象的特点是借助是指示元素存储地址的 指针表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定 逻辑结构，而算法的实现依赖于采用的 存储结构。
(112) 数据类型是一组___________性质相同的值集合以及定义在这个值集合上的一组操作的总称。
(113) 数据对象是___________性质相同的数据元素的集合，是数据的一个子集。
(114) 如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 型运算。引用
(115) 算法的 健壮特性是指做为一个好的算法，当输入的数据非法时，也能适当地做出正确反应或进行相应的处理，而不会产生一些莫名其妙的输出结果。
(116) 算法分析不是针对实际执行时间的精确的算出算法执行具体时间的分析，而是针对算法中语句的 执行次数做出估计，从中得到算法执行时间的信息。
(117) T(n)=O(f(n))，它表示随问题规模n的增大算法的执行时间的增长率和f(n)的增长率 相同，称作算法的渐进时间复杂度，简称时间复杂度。
(118) 若算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法为 原地工作，辅助空间为O(1)。
(119) 在带有头结点的单链表中L中，第一个元素结点的指针是 。L->next (120) 在一个带头节点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。p->next->next
(121) 设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x
的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句: py->next=px->next; px->next=py。
(122) 对于栈操作数据的原则是 。后进先出
(123) 设以数组A[m]存放循环队列的元素，其头尾指针分别为front和rear，则当前队列中的元素个数为 。(rear-front+m)%m
(124) 若已知一个栈的入栈序列是1,2,3,4……n，其输出序列为p1,p2,p3,……pn，若p1= =n,则pi为 。n-i+1
(125) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(126) 通常程序在调用另一个程序时，都需要使用一个 栈来保存被调用程序内分配的局部变量。形式参数的存储空间以及返回地址。
(127) 栈下溢是指在___栈空_____时进行出栈操作。
(128) 用P表示入栈操作，D表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的P和D的操作串为_______ 。PDPPDPDD
(129) 在具有n个单元的循环队列中，队满共有 n-1个元素。
(130) 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
(131) 循环队列的引入，目的是为了克服_______假溢出。
(132) 所谓稀疏矩阵指的是_______非零元很少(t< (133) 在稀疏矩阵表示所对应的三元组线性表中，每个三元组元素按 行为主序， 列号为辅序的次序排列。 (134) 二位数组Am×n按行优先顺序存储在内存中，元素a00地址为loc(a00),每个元素在内存中占d个字节，元素aij的地址计算公式为loc(aij)= loc(a00)＋(i*n+j)*d 。 (135) 树内个结点的度 最大值称为树的度。 (136) 一个二叉树第5层节点最多有 16个。 (137) 已知完全二叉树T的第5层只有7个结点，则该树共有____11____个叶子结点。 (138) 在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______N2+1。 (139) 假设用于通信的电文由8个字母组成，其频率分别为7,19,2,6,32,3,27,10。设计哈夫曼编码，其中字母的编码长度最大是 5位。 (140) 一棵具有257个结点的完全二叉树，它的深度为 。 9 (141) 散列法存储的基本思想是由 关键字的值决定数据的存储地址。 (142) 大多数排序算法都有两个基本的操作： 。比较和移动 (143) 由于查找算法的基本运算是关键字之间的比较操作，所以可用 平均查找长度来衡量查找算法的性能。 (144) 查找有静态查找和动态查找，当查找不成功时动态查找会 将查找关键字插入在表中。 (145) 顺序查找法中设置监视哨，可以起到 防止越界的作用。 (146) 假设列表长度为n，那么查找第i个数据元素时需进行 n-i+1次比较。 (147) 假设查找每个数据元素的概率相等，即Pi=1/n，则顺序查找算法的平均查找长度为： ASL=(n+1)/2。 (148) 折半查找法又称为二分法查找法，这种方法要求待查找的列表必须是 按关键字大小有序排列的顺序表。