哈工大DS-A.docVIP

一、填空题（每空1分，共15分） 若表达式的中缀形式为，则对应的前缀形式为 。若a=1，b=2，c=3，d=4，则后缀形式的结果为 。 用数组存储线性表（15，14，31，10，5，29），用快速排序方法进行递增排序，若排序下标的范围为0～5，选择元素10作为枢轴元素，则调用一趟快速排序算法后，元素10在数组中的的下标位置为 。 从某源点到其余各顶点的Dijkstra算法，若在图的顶点书为10，用邻接矩阵表示图时的计算时间约为10ms，则在图的顶点数为40时，计算时间约为 ms。 如果含n个顶点的图形成一个环，则它有 棵生成树。 若以{4，5，6，7，8，9，10}作为叶子结点的权值构造Huffman树，则其带权路径长度是 。 假定K个关键字互为同义词，若用线性探测再散列法把这K个关键字存入散列表中，至少要进行 次探测。 若已知一个栈的入栈序列是1，2，3，…….，n，其输出序列为，若，则 。 循环队列用数组存放其元素值，已知其头尾指针分别为Front和Rear，则当前队列中的元素个数为 。 从一个具有N个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较 个结点。 在一棵树中，度为1的结点的个数为，度为2的结点的个数为，……，度为m的结点的个数为，则该树有 个叶子结点。 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。 快速排序方法在 情况下最不利于发挥其长处。 已知二叉树有50个叶子结点，则该二叉树的总结点数至少为 。 有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，需要 次比较后才能查找成功。 二、选择题（每题1分，共15分） 下列函数中渐近时间最小的是（ ）。 A． B． C． D． 以下错误的是（ ）。 静态链表即有顺序存储的特点，又有动态链表的优点，所以，它存取表中第i个元素的的时间与i无关。 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 静态链表与动态链表在元素的插入、删除上类似，不需要移动元素。 A．（1），（2） B．（1） C．（1），（2），（3） D．（2） 字符串满足下式，其中Head和Tail的定义同广义表类似，如Head（’xyz’）=’x’，Tail（’xyz’）=’yz’，若Concat（Head（Tail（S））， Head（Tail（Tail（S））））=‘dc’，则S=（ ）。 在一棵具有k层的满三叉树中，结点总数为（ ）。 A． B． C． D． 用DFS遍历一个无环有向图，并在DFS算法退栈返回时，打印出相应的顶点，则输出的顶点序列为（ ）。 A．逆拓扑有序的 B．拓扑有序的 C．与某BFS序列相同 D．无序的 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的的时间复杂度为（ ）。 A． B． C． D． 若在一个大小为6的数组上实现循环队列，且当前Rear和Front的值分别为0和3，当从队列中删除一个元素，在加入两个元素后，Rear和Front的值分别为（ ）。 A．1和5 B．2和4 C．4和2 D．5和1 将一个A[15][15]的下三角矩阵，按行优先存入一维数组B[120]中（A和B的下标均从0开始），A中元素A[6][5]在B数组中的位置k为（ ）。 A．19 B．26 C．21 D．15 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。 A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEBG 在有向图G的拓扑序列中，若顶点在顶点之前，则下列情形不可能出现的是（ ）。 A．G中有弧 B．G