11级数据结构期中试卷评分标准B5
- 格式：doc
- 大小：55.00 KB
- 文档页数：3
1
河北北方学院12-13学年第一学期期中试卷评分标准
数据结构 本科(计算机科学与技术专业11级)
一、单选题（每题2分，共30分）
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
D D B A A D B C D A A D B A C
二填空题（每题2分，共30分）
1、操作对象、关系
2、有穷性、确定性、可行性
3、无
4、其直接前驱结点链域的值（其直接前驱链域的指针）
5、s->next=p;q->next=s;
6、1,3,5,7,9
7、’bcdef’
8、cp->front==(cp->rear+1)%QueuSize
(cp->rear-cq->front==QueueSize)
9、行下标（行标）、列下标（列标）、元素值（数值）
10、80
11、n+1
12、63
13、Ltag=0
14、64
15、2~k-1
填一个空的题填空错误扣2分；填两个空的题每个填空错误扣1分；填三个空
的全错扣2分，否则扣1分；
三、简答题（每题5分，共20分）
1、试举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其运算
效率不同。（5分）
答：线性表执行删除的操作，如果是顺序存储，时间复杂度是O（n），而链式存储，
时间复杂度是O(1)
只要列举的是同一种运算下，分别阐述了和顺序存储和链式存储不同的运算效率的
都算正确。
2、
已知一棵二叉树的中序遍历序列为cbafehgd，后序遍历序列cbfhgeda，画出该
二叉树，并求出该二叉树的先序遍历序列。（5分）
答：先序：a b c d e f h g(2分)
2
画出该二叉树(3分)
3、已知森林F如图所示，请画出其对应的二叉树BT（5分）
答：
4、请用分别以8，11，13，5，17，25，21作为权值的叶结点，构造一棵哈夫曼树，
并求该二叉树的带权路径长度。（5分）
答：构造一棵哈夫曼树（3分）
A
B C
J E D F
G
H I
3
带权路径长度=267（2分）
四、算法设计题（每题10分，共20分）
1、已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个
删除表中所有值小于max但大于min的元素的算法。
Typedef struct lnode
{ int data ;
struct lnode *next;
} lnode , *linklist ;
void delete(linklist &l,int max,int min)
{
pre=l;p=l->next;
while(p)
{if (p->data
{pre->next= p->next;
free(p);
p=pre->next;
}
else {pre=p;
p=p->next;
}
}
}
2、设一棵二叉树T以二叉链表为存储结构，编写算法求该二叉树叶子结点的数目。
Typedef struct BiTnode
{ Telemtype data;
Struct Bitnode *lchild,*rchild;
}BiTnode,*Bitree;
int leaf_count(Bitree BT)
{
if (BT==null) return 0;
else if (BT->lchild==null&& BT->rchild==null) return 1;
else return leaf_count(BT->lchild)+ leaf_count(BT->rchild);
}
非递归运算也算正确
