《16春天大《数据结构》在线作业一》由会员分享,可在线阅读,更多相关《16春天大《数据结构》在线作业一(7页珍藏版)》请在金锄头文库上搜索。
1、数据结构在线作业一 一、单选题(共 40 道试题,共 100 分。 )1. 设二叉排序树中有 n 个结点,则在二叉排序树的平均平均查找长度为( ) 。. O(1) . O(log2n) . O(n4) . O(n2 ) 正确答案: 2. 对一个满二叉树,m 个树叶,n 个结点,深度为 h,则() 。. n=h+m . h+m=2n . m=h-1 . n=2 的 h 次方-1 正确答案: 3. 设一维数组中有 n 个数组元素,则读取第 i 个数组元素的平均时间复杂度为( ) 。. O(n) . O(nlog2n) . O(1) . O(n2 ) 正确答案: 4. 已知某二叉树的后序遍历序列是,
2、中序遍历序列是,它的前序遍历序列是() 。. . . . 正确答案: 5. 以下数据结构中哪一个是非线性结构?( ) . 队列 . 栈 . 线性表 . 二叉树 正确答案: 6. 向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时,则执行() 。(不带空的头结点) . HSnxt=s; . snxt= HSnxt;HSnxt=s; . snxt= HS;HS=s; . snxt= HS;HS= HSnxt; 正确答案:7. 设某强连通图中有 n 个顶点,则该强连通图中至少有( )条边。. n(n-1) . n+1 . n . n(n+1) 正确答案: 8. 一个栈的入栈序列, , , ,
3、,则栈的不可能的输出序列是() 。. . . . 正确答案: 9. 若已知一个栈的入栈序列是 1,2,3,n,其输出序列为 p1,p2,p3,pn,若 p1=n,则 pi 为() 。. i . n=i . n-i+1 . 不确定 正确答案: 10. 在二叉排序树中插入一个结点的时间复杂度为( ) 。. O(1) . O(n) . O(log2n) . O(n2 ) 正确答案: 11. 对 n 个记录的文件进行快速排序,所需要的辅助存储空间大致为( ) . O(1) . O(n) . O(1og2n) . O(n2) 正确答案: 12. 设一组初始关键字记录关键字为(20,15,14,18,21
4、,36,40,10),则以 20 为基准 记录的一趟快速排序结束后的结果为( )。 . 10,15,14,18,20,36,40,21 . 10,15,14,18,20,40,36,21 . 10,15,14,20,18,40,36,2l . 15,10,14,18,20,36,40,21 正确答案: 13. 一个队列的数据入列序列是 1,2,3,4,则队列的出队时输出序列是() 。 . 4,3,2,1 . 1,2,3,4 . 1,4,3,2 . 3,2,4,1 正确答案:14. 设哈夫曼树中的叶子结点总数为 m,若用二叉链表作为存储结构,则该哈夫曼树中总 共有( )个空指针域。. 2m-1
5、. 2m . 2m+1 . 4m 正确答案: 15. 二维数组中,每个元素的长度为 3 个字节,行下标 i 从 0 到 7,列下标 j 从 0 到 9,从 首地址 S 开始连续存放在存储器内,该数组按列存放时,元素47的起始地址为() 。. S+141 . S+180 . S+222 . S+225 正确答案: 16. 在数据结构中,从逻辑上可以把数据结构分成() 。 . 动态结构和静态结构 . 紧凑结构和非紧凑结构 . 线性结构和非线性结构 . 内部结构和外部结构 正确答案: 17. 设串 s1=FG,s2=PQRST,函数 on(x,y)返回 x 和 y 串的连接串,sus(s,i,j)返
6、回串 s 的从序号 i 的字符开始的 j 个字符组成的子串,ln(s)返回串 s 的长度,则 on(sus(s1,2,ln(s2),sus(s1,ln(s2),2)的结果串是() 。. F . FG . PQRST . FF 正确答案: 18. 设无向图的顶点个数为 n,则该图最多有( )条边。. n-1 . n(n-1)/2 . n(n+1)/2 . 0 正确答案: 19. 设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称作() 。 . 连接 . 模式匹配 . 求子串 . 求串长 正确答案: 20. 在一棵具有 5 层的满二叉树中结点数为( ). 33 . 32 . 31.
7、31 正确答案: 21. 设一棵二叉树的深度为 k,则该二叉树中最多有( )个结点。. 2k-1 . 2k . 2k-1 . 2k -1 正确答案: 22. 在以下的叙述中,正确的是() 。 . 线性表的顺序存储结构优于链表存储结构 . 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 . 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 . 线性表的链表存储结构优于顺序存储结构 正确答案: 23. 设串的长度为 n,则它的子串个数为() 。. n . n(n+1) . n(n+1)/2 . n(n+1)/2+1 正确答案: 24. 哈希表中的冲突可以通过改变哈希函数完全避免。 .
8、 正确 . 错误 正确答案: 25. 任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序() 。 . 不发生改变 . 发生改变 . 不能确定 . 以上都不对 正确答案: 26. 设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要进行( )趟的分配和回收才能使得初始关键字序列变成有序序列。. 3 . 4 . 5 . 8 正确答案: 27. 从一个栈顶指针为 HS 的链栈中删除一个结点时,用 x 保存被删结点的值,则执行() 。 (不带空的头结点) . x=HS;HS= HSnxt; . x=HSt; . HS=HSnxt;x=HSt; . x=HSt
9、;HS= HSnxt; 正确答案:28. 若有 18 个元素的有序表存放在一维数组19中,第一个元素放1中,现进行二分查 找,则查找3的比较序列的下标依次为( ) . 1,2,3 . 9,5,2,3 . 9,5,3 . 9,4,2,3 正确答案: 29. 设指针变量 p 指向单链表中结点,若删除单链表中结点,则需要修改指针的操作序列 为( ) 。 . q=p-nxt;p-t=q-t;p-nxt=q-nxt;fr(q); . q=p-nxt;q-t=p-t;p-nxt=q-nxt;fr(q); . q=p-nxt;p-nxt=q-nxt;fr(q); . q=p-nxt;p-t=q-t;fr(q
10、) 正确答案: 30. 从一个具有 n 个结点的单链表中查找其值等于 x 结点时,在查找成功的情况下,需平 均比较()个结点。. n . n/2 . (n-1)/2 . (n+1)/2 正确答案: 31. 常对数组进行的两种基本操作是() 。 . 建立与删除 . 索引和修改 . 对数据元素的存取和修改 . 查找与索引 正确答案: 32. 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时,若选用 H(K)=K %9 作为散列函数,则散列地址为 1 的元素有( )个. 1 . 2 . 3 . 4 正确答案: 33. 假定在一棵二叉树中,双分支结点数为 15,单分支结点数为
11、30 个,则叶子结点数为 ()个。. 15 . 16 . 17 . 47 正确答案: 34. 设无向图 G 中有 n 个顶点,则该无向图的最小生成树上有( )条边。. n . n-1. 2n . 2n-1 正确答案: 35. 某二叉树的前序遍历结点访问顺序是 gfh,中序遍历的结点访问顺序是 ghf,则其后序 遍历的结点访问顺序是() 。. gfh . gfh . ghf . ghf 正确答案: 36. 判定一个循环队列 QU(最多元素为 m0)为空的条件是() 。. rr - front= =m0 . rr-front-1= =m0 . front= = rr . front= = rr+1
12、 正确答案: 37. 设顺序循环队列 Q0:M-1的头指针和尾指针分别为 F 和 R,头指针 F 总是指向队头元 素的前一位置,尾指针 R 总是指向队尾元素的当前位置,则该循环队列中的元素个数为( ) 。. R-F . F-R . (R-F+M)M . (F-R+M)M 正确答案: 38. 数据结构 S(t Strut)可以被形式地定义为 S=(,R) ,其中是()有限集合,R 是上的 关系有限集合。 . 算法 . 数据元素 . 数据操作 . 数据对象 正确答案: 39. 二维数组中,每个元素的长度为 3 个字节,行下标 i 从 0 到 7,列下标 j 从 0 到 9,从 首地址 S 开始连续存放在存储器内,存放该数组至少需要的字节数是() 。. 80 . 100 . 240 . 270 正确答案: 40. 链式存储在插入和删除时需要保持物理存储空间的顺序分配,不需要保持数据元素之 间的逻辑顺序。 . 正确 . 错误 正确答案: