交大数据结构012-2013试卷

更新时间:2024-01-02 15:52:01 阅读量: 教育文库 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

北 京 交 通 大 学 考 试 试 题 (A卷)

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:(1)本试卷共有六道大题,(2)答案一律写在答题纸上,(3)试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题(每空2分,共20分)

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD,中序遍历该二叉树的序列为BADC,则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =(D,R),D={1,2,3,4,5},R={r},

r={<1,2>,<2,4>,<4,5>,<1,3>,<3,2>,<3,5>},则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19,22,01,38,10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50,度数为1的结点数为30,则该二叉树中总

共有_______个结点。

7. 设哈夫曼树中共有n个结点,则该哈夫曼树中有________个度数为1的结点。

8. 简单选择排序和直接插入排序算法的平均时间复杂度为___________。

二、 选择题(每题2分,共20分)

1. 设一条单链表的头指针变量为head且该链表没有头结点,则其判空条件是( )。 (A) head==NULL (B) head->next==NULL (C) head->next==head (D) head!=NULL

2. 设指针变量front表示链式队列的队头指针,指针变量rear表示链式队列的队

尾指针,指针变量s指向将要入队列的结点X,则入队列的操作序列为( )。

(A) front->next=s;front=s; (B) s->next=rear;rear=s; (C) rear->next=s;rear=s; (D) s->next=front;front=s;

3. 设一组权值集合W={2,3,4,5,6},则由该权值集合构造的哈夫曼树中带权路

径长度之和为( )。 (A) 20 (B) 30 (C) 40 (D) 45

4. 设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个

数分别为( )。 (A) n,e (B) e,n (C) 2n,e (D) n,2e

5. 设一组初始记录关键字序列为(345,253,674,924,627),则用基数排序需要

进行( )趟的分配和收集才能使得初始关键字序列变成有序序列。 (A) 3 (B) 4 (C) 5 (D) 8

6. 函数substr(“DATASTRUCTURE”,5,9)的返回值为( )。 (A) “STRUCTURE” (B) “DATA”

(C) “ASTRUCTUR” (D) “DATASTRUCTURE”

7. 下面程序的时间复杂为( )

for(i=1,s=0; i<=n; i++){t=1;for(j=1;j<=i;j++) t=t*j;s=s+t;}

234

(A) O(n) (B) O(n) (C) O(n) (D) O(n)

8. 深度为k的完全二叉树中最少有( )个结点。

k-1k-1k-1k

(A) 2-1 (B) 2 (C) 2+1 (D) 2-1

9. 设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度为

( )。

2

(A) O(n) (B) O(n) (C) O(nlog2n) (D) O(1og2n)

10. 稀疏矩阵是指___ _ (A) 行数,列数和的矩阵 (B) 有少量零元素的矩阵 (C) 有少量非零元素的矩阵 (D) 元素少的矩阵 三、 判断题(每题1分, 共10分)

1. 调用一次深度优先遍历可以访问到图中的所有顶点。( ) 2. 分块查找的平均查找长度不仅与索引表的长度有关,而且与块的长度有关。

( )

3. 冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。( ) 4. 当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。( )

5. 设一棵二叉树的先序序列和后序序列,则能够唯一确定出该二叉树的形状。

( )

6. 层次遍历初始堆可以得到一个有序的序列。( )

7. 设一棵树T可以转化成二叉树BT,则二叉树BT中一定没有右子树。( ) 8. 线性表的顺序存储结构比链式存储结构更好。( ) 9. 中序遍历二叉排序树可以得到一个有序的序列。( ) 10. 带权无向图的最小生成树是唯一的。( )

四、 应用题(24分)

1.(6分)下图所示的森林:

(1) 求树(a)的先根序列和后根序列; (2) 求森林先序序列和中序序列; (3)将此森林转换为相应的二叉树;

ABD(a)CEFIGHJ(b)K

2.(6分)给定下列图,完成以下问题 (1)画出该图的邻接矩阵和邻接表

(2)根据所画的邻接表,从顶点V0出发,画出图的深度优先搜索树

(3)根据普里姆(Prim)算法,求它的最小生成树(不必写出全部过程,在生成树中标出边生成的次序即可)

v08v2242v6v3756v448v17v58v7 3.(6分)设哈希表HT表长m为13,哈希函数为H(k)=k MOD m,给定的关键值

序列为{19,14,23,10,68,20,84,27,55,11}。试求出用线性探测法解决冲突时所构造的哈希表,并求出在等概率的情况下查找成功的平均查找长度ASL。

4.(6分)将序列(10,18,4,3,6,12,1,9,18+,8)中的关键字按升序重新排列,请写出

(1)冒泡排序一趟扫描的结果

(2)以第一个元素为分界点的快速排序一趟扫描的结果 (3)希尔排序每趟的排序结果(增量为5,3,1) (4)堆排序所建的初始堆和第一趟排序结果。

五、 程序阅读题(10分)

1.(5分)阅读下面的算法

LinkList mynote(LinkList L)

{//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L;L=L->next;p=L; S1: while(p->next) p=p->next; S2: p->next=q;q->next=NULL; }

return L; }

请回答下列问题:

(1)说明语句S1的功能; (2)说明语句组S2的功能;

(3)设链表表示的线性表为(a1,a2, ?,an),写出算法执行后的返回值所表示的线性表。

2. (5分)已知二叉树的存储结构为二叉链表,阅读下面算法。

typedef struct node { DateType data; Struct node * next; }ListNode;

typedef ListNode * LinkList ; LinkList Leafhead=NULL; void Inorder (BinTree T) {

LinkList s; if(T){

Inorder(T->lchild);

if ((!T->lchild)&&(!T->rchild)){

s=(ListNode*)malloc(sizeof(ListNode)); s->data=T->data;

s->next=Leafhead; Leafhead=s; }

Inorder(T->rchild); } }

对于如下所示的二叉树

(1)画出执行上述算法后所建立的结构;

(2)说明该算法的功能。

六、 算法设计题(16分)

算法书写要求:应简单阐述算法的主要思想,对关键变量和关键语句进行注释;如果为递归算法,则应说明递归调用的初始条件,否则扣分。写出正确的设计思想和伪代码可以酌情给分。

如果算法中用到堆栈,可直接调用下列操作: InitStack(S): 栈初始化

push(S,x): 将元素x推入栈S;(插入) pop(S,x): 将栈顶元素存入变量x中;(删除)

StackEmpty(S): 判别栈S是否为空,如果是,返回1,否则返回0

如果算法中用到队列,可直接调用下列操作: InitQueue(Q): 队列初始化

EnQueue(Q,x): 将元素x加入队列Q;(插入) DeQueue(Q,x): 取出队头元素,放入变量x中;(删除)

QueueEmpty(Q): 判别队列Q是否为空,如果是,返回1,否则返回0

1.(8分)下列题中任选一题

(1)设有一个由正整数序列组成的有序单链表(递增有序,且允许有相等的整数存在),试编写算法,确定在序列中比正整数x大的数有几个(相同的数只计算一次,如序列{20, 20, 17,16,15,15,11,10,8,7,7,5,4})中比10大的整数有5个;) (2)设计在单链表中删除值相同的多余结点的算法; (3)设计在单链表上实现简单选择排序算法。

链表结构定义为: typedef struct Lnode{

ElemType data; struct Lnode *next; }LNode, *LinkList;

2. (8分) 下列题中任选一题 (1)设计一个求结点x在二叉树T中的双亲结点算法。若没有值为x的结点或没有双亲结点,分别打印出相应的信息;若结点x有双亲,打印其双亲结点的值。 (2)二叉树按二叉链表形式存储,编写一个算法判别给定的二叉树是否为完全二叉树。

(3)在二叉排序树的结构中,有些数据元素值可能是相同的,设计一个算法实现按递增顺序打印结点的数据域,要求相同的数据元素仅输出一个,算法还能报出最后被滤掉而未输出的数据元素个数。对如下图所示的二叉排序树,输出为10,12,13,15,18,21,27,35,42, 滤掉3个元素。

181310121518182721273542

二叉树T采用如下定义的存储结构: typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;

链表结构定义为: typedef struct Lnode{

ElemType data; struct Lnode *next; }LNode, *LinkList;

2. (8分) 下列题中任选一题 (1)设计一个求结点x在二叉树T中的双亲结点算法。若没有值为x的结点或没有双亲结点,分别打印出相应的信息;若结点x有双亲,打印其双亲结点的值。 (2)二叉树按二叉链表形式存储,编写一个算法判别给定的二叉树是否为完全二叉树。

(3)在二叉排序树的结构中,有些数据元素值可能是相同的,设计一个算法实现按递增顺序打印结点的数据域,要求相同的数据元素仅输出一个,算法还能报出最后被滤掉而未输出的数据元素个数。对如下图所示的二叉排序树,输出为10,12,13,15,18,21,27,35,42, 滤掉3个元素。

181310121518182721273542

二叉树T采用如下定义的存储结构: typedef struct BiTNode {

TElemType data;

struct BiTNode *lchild, *rchild; }BiTNode, *BiTree;

本文来源:https://www.bwwdw.com/article/2w5x.html

Top