大工16春《数据结构》开卷考试复习资料

-是机密被发动之前大连理工大学网络教育学院2016年9月数据结构课程期末复习资料注意事项：本复习题满分共400分。一、个别选题(本大题共65小题，每小题3分，共195分)1 .在该算法中，该请求被称为()，从而即使在未授权数据被输入时也能进行适当的处理。(a ) .正确性(b ) .可行性(c ) .顽强性(d ) .输入性2 .当s是c语言的句子，计算机执行以下算法时，算法的时间复杂度为()for(i=n-1； i=0； i- )for(j=0； jright=s； s-left=p； p-right-left=s； s-right=p-right；(B) s-left=p； s-right=p-right； p-right=s； p-right-left=s；(C) p-right=s； p-right-left=s； s-left=p； s-right=p-right；(D) s-left=p； s-right=p-right； p-right-left=s； p-right=s；12 .图中的Depth-First Search(DFS )扫描思想实际上是二叉树()扫描方法的普及。(a )、顺序(b )、顺序(c )、顺序(d )、层顺序13 .在上图的链队q中，元素a离开队伍的操作序列为()(a )，p=Q.front-next； p-next=Q.front-next；(b )，p=Q.front-next； Q.front-next=p-next；(c )，p=Q.rear-next； p-next=Q.rear-next；(d )，p=Q-next； Q-next=p-next；14 .霍夫曼树的带宽加权路径长度WPL等于(a )、除根节点以外的所有节点的权重之和(b )、所有节点的权重之和(c )、各叶节点加权路径长度之和(d )、根节点的值15 .线索二叉链表利用()域存储后续节点的地址。(a )、lchild (B )、data (C )、rchild (D )、root16 .构成数据的基本单位是()(a )数据项目(b )数据类型(c )数据要素(d )数据变量假设数据结构A=(D，r )，其中d= 1，2，3，4 ，R=r，r= 1，2，2，3，3，4，4，1 ，则数据结构a为()(a )线性结构(b )树结构(c )地图结构(d )集合18 .数组的逻辑结构不同于以下()的逻辑结构：(a )线性表(b )堆栈(c )队列(d )树19 .二叉树中第I个(I1 )层上的节点数最大为()个。A.2i B.2i 1 C.2i-1 D.2i 220 .一个算法的评估不包括以下()内容。a .健壮性和可读性b .并行性c .准确性d .时空复杂性21 .执行以将指针p指向的节点插入具有开头节点的链接表HL的头中。A. p-next=HL-next； HL-next=p； B. p-next=HL； HL=p；C. p-next=HL； p=HL； D. HL=p； p-next=HL；22 .对于线性表，在以下哪种情况下应采用链接表？ （）a .经常需要访问元素b。 经常需要插入和删除c .表的要素必须占据连续的存储区域d。 表格要素的数量不变23 .堆栈的输入序列为1 2 3时，以下序列不能成为堆栈的输出序列()A. 2 3 1 B. 3 2 1C. 3 1 2 D. 1 2 324 .在以下各种排序算法中，平均时间复杂度O(n2)为()(a )快速排序(b )堆栈排序(c )合并排序(d )冒泡排序25 .输入序列1、2、3、n被堆叠之后，输出序列的第一个元素由n表示，从而输出序列的第I个输出元素由()表示。(A) n-i(B) n-1-i(C) n l -i(D )不能确定26 .优选的是，散列表具有m个存储单元，如果散列函数H(key)=key % p，则p选择为()(a)m以下的最大奇数(b)m以下的最大素数(c)m以下的最大偶数(d)m以下的最大总数27 .如果一个频数为3的树，频数为3的节点数为2个，频数为2的节点数为1个，频数为1的节点数为2个，则频数为0的节点数为()个。(A) 4(B) 5(C) 6(D) 728 .假设完全无向图有n个顶点，那么该完全无向图有()条边。(a ) n (n-1 )/2 (b ) n (n-1 ) (c ) n (n1)/2 (d ) (n-1 )/229.AOV网是一种()a .有向图b .无向图c .无向无环图d .无向无环图30 .使用开放地址法处理哈希表冲突时，其平均查找长度()a .低于链接法的处理冲突b .高于链接法的处理冲突c .链接法的处理冲突同样高于d .二分搜索31 .需要利用形参直接访问实参时，请将形参变量作为()参数进行说明。a .值b .函数c .指针d .参照32 .对于具有稀疏矩阵的行指针向量的链路存储，每个链路表中的节点具有相同的()a .行号b .列号c .要素值d .非零要素数33 .快速排序最差情况下的时间复杂性是()a.o (log2n ) b.o (nlog 2n ) c.0 (n ) d.0 (n2)34 .从二叉搜索树中查找元素时，其时间复杂度几乎为()A. O(n) B. O(1) C. O(log2n) D. O(n2)35 .如果指针变量p指向单链路表中的节点a，那么删除节点a的后续节点b所需的操作是()(a ) p-next=p-next-next (b ) p=p-next(C) p=p-next-next (D) p-next=p36 .一种堆栈s的容量至少为()，只要堆栈s与队列q均为空，元素E1、E2、E3、E4、E5和E6依次通过堆栈s，在一个元素被堆栈之后进入队列q，并且六个元素列出的次序分别是E2、E4、E3、E6、E5和E1(A) 6 (B) 4 (C) 3 (D) 2当将37.10阶对称矩阵的压缩存储在一维阵列a中时，阵列a的长度变为最小()(A) 100 (B) 40 (C) 55 (D) 8038 .如果在节点a有3个兄弟节点，并且节点b是节点a的父节点，则节点b的度数为()(A) 3 (B) 4 (C) 5 (D) 139 .由二叉树的定义可知，具有3个节点的二叉树共有()种不同的形态。(A) 4 (B) 5 (C) 6 (D) 740 .以下四种排序方法使()的空间复杂性最大：(a )起泡排序(b )快速排序(c )堆积排序(d )水蛭排序41 .如果某个无向图有n个顶点，那么该无向图的邻接表中有()个点头。(A) 2n(B) n(C) n/2(D) n(n-1 )42 .假设无向图g有n个顶点，那么该无向图的最小生成树有()条边。(A) n(B) n-1(C) 2n(D) 2n-143 .如果将初始记录的一系列关键字设为(60，80，55，40，42，85 )，则以第一个关键字60为基准得到的快速排序结果为()(a ) 40、42、60、55、80、85 (b ) 42、45、55、60、85、80(c ) 42，40，55，60，80，85 (d ) 42，40，60，85，55，8044.()二叉排序树可以得到从小到大的有序。(a )顺序遍历(b )顺序遍历(c )顺序遍历(d )层次遍历45 .如果从上到下、从左到右以1的顺序对完全二叉树进行编号，则编号为I节点左侧的子节点的编号为()(A) 2i 1(B) 2i(C) i/2(D) 2i-146 .段s=i=0； do i=i 1； s=s i； while(i=n )的时间复杂度为()(a ) o (n ) (b ) o (nlog2n ) (c ) o (n2) (d ) o (n3/2)47 .如果将带头节点的单向链接表的头指针变量设为head，则其判定空条件为()(a )头=0(b )头-下一个=0(c )头下一个=头(d )头！=048 .设某二叉树的高度为10，则该二叉树叶的节点最多()(A) 20(B) 256(C) 512(D) 102449 .若设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134 )，则为了利用二分法检索关键字90而应比较关键字数为()(A) 1(B) 2(C) 3(D) 450 .如果指针变量top指向当前链堆栈的堆栈顶点，则删除堆栈顶点元素的操作序列为()(A) top=top 1 (B) top=top-1(c )上一步=上