PDF《2014 年春季北大《数据结构与算法 B》期末考试模拟试卷》

2014 年春季北大《数据结构与算法 B》期末考试模拟试卷 (本试卷只是给同学们看看考题形式和范围,难度与真实考卷稍有差别) 学号_姓名_教师/教室_ (注:如未标明,本试卷题中的下标、位置都从

0 开始计数)

一、填空题(共32 分) 1.

设有字符串变量 String A = "This", B="is", C="just", D="a?test",请计算下列表达式: (1)A+B+D= (2)D.IndexOf("t") = " " (3)B.Strlength() = (4)D.SubStr(1,2) =" " 2. 顺序查找 n 个元素的顺序表,若查找成功,则比较关键字的次数最多为 次;

若 查找失败,则比较关键字的次数最多为 ,最少为 次. 3. 在散列函数 H(key)=key%p 中,p 值最好取 . 4. 对于下图邻接表所对应的有向图,试写出: (1) 从顶点①出发进行深度优先遍历结果 ;

(2) 从顶点①出发进行广度优先遍历结果 ;

5. 当图中各条边上的权值 时,宽度优先搜索算法可用来解决单源最短路径问题? 6. 一棵有 n 个结点的满二叉树有 个度为

1 的结点、 有 个分支 (非终端) 结点;

该满二叉树的深度最大为 , 最小为 . (独根树深度为 0) 7. 对于给定的 n 个元素,可以构造出的逻辑结构有 , , , 四种. 8. 下面程序段的时间复杂度为 .(n>1) [大O表示法] 【2 分】 sum=1;

for (i=0;

sumlchild == null) lh = ;

else lh = ;

if (p->rchild == null) rh = ;

else rh = ;

if (lh > rh) hi = ;

else hi = ;

} else hi = ;

return hi;

} 2. 对单链表 (带头结点) 中元素按插入方法实现非递增序列的排序的 C 语言描述算法如下, 其中 L 为链表头结点指针.请填充算法中标出的空白处,完成其功能. typedef struct node { int da ta;

struct node *next;

} linknode, *link;

void Insertsort(link L) { link p,q, r, u;

p = L->next;

;

while ( ) { r=L;

q=L->next;

while (q != NULL && q->data data) { r=q;

q=q->next;

} u=p->next;

;

;

p=u;

} }