2021 西安交通大学软件 915 考试试卷
考试时间:
180
分钟
一、单选题(10 小题,每题 2 分,共 20 分)
1.C 语言中用于获取字符串长度的函数名是( )
A、strlen B、strcpy
C、strcat D、strcmp
2. 在单链表中引入头结点后带来的好处是( )
A、标识链表中首结点的位置
B、统一操作,而无须进行特殊处理
C、使单链表至少有一个结点
D、显示说明单链表的长度
3. 一个带权无向连通图的最小生成树( )
A、一定有多颗 B、只有一颗
C、可以有一颗或多颗 D、可能不存在
4. 设有一个顺序共享栈 Share[0:n-1],其中第一个栈顶指针 top1 的初始值为-1,第二个栈顶指
针 top2 的初始值为 n,则判断共享栈满的条件是( )
A、top2-top1==1 B、top1-top2==1 C、top1==top2 D、以上都不对
5. 若 union(x, y)代表并查集合并两个结点的操作,在不考虑带权合并与按秩合并的前提下,操
作序列 union(1, 2),union(3, 1),union(3, 4),union(2, 5)所对应的合并树可能为( )
6. 以下哪种数据结构中最适合表示一本书的书名、目录、章节( )
A、HashTable B、BST C、Tree D、List
7. 对一个采用邻接表存储的图进行深度优先遍历的过程类似于对二叉树 遍历( )
A、前序 B、中序 C、层序 D、后序
8. 设顺序循环队列 Q[0: m-1]的头指针和尾指针分别为 front 和 rear,头指针 front 总是指向
队头元素的前一位置,尾指针 rear 总是指向队尾元素的当前位置.则该循环队列中的元
素个数为( )
A、(rear-front+m)%m B、rear-front+1 C、(front-rear+m)%m D、rear-front
9. 以下四种排序算法中属于稳定排序的是( )
A、选择排序 B、冒泡排序 C、希尔排序 D、堆排序
10. 以下关于设计一个好的算法应该达到的目标中叙述错误的是( )
A、健壮性:当环境发生变化时,算法能适当地做出反应或进行处理,不会产生不需
要的运行结果
B、可读性:算法应易于阅读和理解,以便调试、修改和扩充
C、高效性:算法能达到所需要的的时间和空间性能
D、正确性:算法应能正确地实现预定的功能
二、判断题(在括号内打上“√”或“×”)(5 小题,每题 2 分,共 10 分)
11. 任意一个大根堆都可以在线性时间内调整为小根堆。( )
12. 一棵 n 个结点的二叉树任意两个子树的高度差绝对值小于等于 2,则该二叉树的高度
为 。( )
13. 广义表的表尾都是广义表。( )