数据结构（专科） 第 1次自检自测 一、单选题（每小题 2分，共 8分） 1.执行下面的程序段时，执行 S语句的次数为（ D ） for ( int i=1 ; i <=n ; i++ ) for ( int j=1 ; j <= i ; j++ ) S ; A. n2 B. n2/2 C.n (n+1) D.n (n+1)/2 2.请指出下面二元组表示的数据结构属于何种结构。（ B ） D＝（K，R） K＝（1，2，3，4，5） R＝｛（1，2），（1，5），（2，3），（2，4）｝ A. 线性表 B. 树 C. 集中 D. 图 3.在单链表 HL中，若要在指针 q所指向结点的后面插入一个由指针 p所指向的结点，则执行（ D ） A. q－>next ＝ p－>next ; p－>next ＝ q ; B. p－>next ＝ q－>next ; q ＝ p ; C. q－>next ＝ p－>next ; p－>next ＝ q; D. p－>next ＝ q－>next ; q－>next ＝ p ; 4.当利用大小为 N的数组顺序存储一个栈时，假定用 top＝＝N表示栈空，则向这个栈插入一个元素时，首先应执行（ C ）语句修改 top指针。 A.top＋＋ B. top=0 C. top―― D. top＝－1 二、填空题（每空 1分，共 23分） 1. 一个算法的时间复杂度为（4n2＋2nlog2n＋3n－7）/ (5n)，其数量级表示为（ O（n） ）。 2. 对于线性表（11，43，15，50，30，22，94，72）进行散列存储时，若选用 H(K)=K%8作为散列函数，则散列地址为 0的元素有（ 1 ）个，散列地址为 3的元素有（ 2 ）个，散列地址为 6的元素有（ 3 ）个。 3. 从一个数组 a[7]中顺序查找元素时，假定查找第一个元素 a[0]的概率为 1/3，查找第二个元素 a[1]的概率为 1/4，查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为（ 35/12 或 2.92 ）。 4. 队列的插入操作在（ 队尾 进行，删除在（ 队首 ）进行；而栈的插入与删除均在（栈顶 ）进行。 5. 在一个顺序队列 Q中，判断队空的条件为（ Q.front＝＝Q.rear ）,判断队满的条件为（ （Q.rear＋1）%Maxsize＝＝Q.front ） 6. 中缀表达式 7×（8＋x）－5/（y－3） 所对应的后缀表达式为：（ 7 8 x ＋ × 5 y 3 － / － ） 7. 在一棵 5层的完全二叉树中，结点数最多为（ 31 ）个，结点数最少为（ 16 ）个。 8. 对于一棵具有 n个结点的二叉树，若一个结点的编号为 i(0≤i≤n－1)，则它的左孩子结点的编号为（ 2i＋1），右孩子结点的编号为（ 2i+2），双亲结点的编号...
