广东专插本2014年本科插班生考试计算机科学与技术专业数据结构
2015-11-14 17:50
感兴趣的有：
人
广东专插本2014年本科插班生考试试卷
计算机科学与技术专业 数据结构 试卷（A卷）
一、 单项选择题（每题2分，共30分）
|
题号 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
答案 |
|
|
|
|
|
|
|
|
|
|
|
题号 |
11 |
12 |
13 |
14 |
15 |
|
|
|
|
|
|
答案 |
|
|
|
|
|
|
|
|
|
|
1. 栈和队列的共同特点是( )。
A. 只允许在端点处插入和删除元素 B. 都是先进后出
C. 都是先进先出 D. 没有共同点
2. 用链接方式存储的队列，在进行插入运算时( )。
A. 仅修改头指针 B. 头、尾指针都要修改
C. 仅修改尾指针 D. 头、尾指针可能都要修改
3. 以下数据结构中哪一个是非线性结构？( )
A. 队列 B. 栈 C. 线性表 D. 二叉树
4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？
A．688 B．678 C．692 D．696
5. 树最适合用来表示( )。
A.有序数据元素 B.无序数据元素
C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据
6. 二叉树的第k层的结点数最多为( )。
A．2k-1 B.2K+1 C.2K-1 D. 2k-1
7. 设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（ ）。
A. 1,2,3,4 B. 2,3,4,1 C. 1,4,2,3 D. 1,2,4,3
8. 下列关于数据结构的叙述中，正确的是 （ ）。
A. 数组是同类型值的集合 B. 树是一种线性结构
C. 一般情况下递归算法的程序结构更为精炼、效率更高
D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点
9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K % 9作为散列函数，则散列地址为1的元素有（ ）个。
A．1 B．2 C．3 D．4
10. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
11. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。
A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;
C. p->next=HL; p=HL; D. HL=p; p->next=HL;
12. 线性表采用链式存储时，结点的存储地址（ ）。
A．必须是不连续的 B．连续与否均可
C．必须是连续的 D．和头结点的存储地址相连续
13. 任何一个无向连通图的最小生成树（ ）。
A. 只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在
14. 设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。
A. p->next=p->next->next B. p=p->next
C. p=p->next->next D. p->next=p
15. 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。
A. BCDA B. BADC C. CDAB D. CBDA
二、填空题（每空2分，共20分）
1. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
2. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则该树的深度为___________，树的度为_________。
3. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
4. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________________个指针是空指针。
5. 有如下递归函数：
void f( int w )
{ int i;
static int j=1;
if (w>0){
printf(“%d:”,j++);
for ( i=1; i<=w; i++ ) printf( “%d，”, w );
printf( “\n” );
f( w −1 );
}
}
调用语句f(3)的结果是______________________________。
6. 已知一有向图的邻接表存储结构如下：从顶点1出发，DFS遍历的输出序列是______________，BFS遍历的输出序列是________________。
三、判断题（对的划√，错的划×。每小题1分，共10分）
（ ）1．调用一次深度优先遍历可以访问到图中的所有顶点。
（ ）2．哈夫曼树上只有树叶或者双支结点。
（ ）3．冒泡排序在初始关键字序列为递减有序的情况下执行的交换次数最多。
（ ）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
（ ）5．已知一棵二叉树的先序序列和后序序列，则能够唯一确定该二叉树的形状。
（ ）6．层次遍历二叉树需要用到堆栈作为辅助结构。
（ ）7．一棵树按孩子兄弟法转化成二叉树，该二叉树中一定没有右子树。
（ ）8．线性表的顺序存储结构比链式存储结构更好。
（ ）9．可以在有序单链表中实现二分查找算法。
（ ）10. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。
四、程序填空题（每个空2分，共10分）
1. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
#define M 100
typedef struct {
int s[M];
int top;
} sqstack;
void push( sqstack *stack, int x )
{
if (stack->top==M-1) printf(“overflow”);
else {
______________________;
_____________________;
}
}
2．下面算法是求二叉树双支个数的算法。请完成填空。
struct TreeNode{
int data;
struct TreeNode *left, *right;
};
int fnGetLeaf( TreeNode *T )
{
if(____________________) return 0;
if( T->left!=NULL && T->right!=NULL)
return (____________________________________________);
else return(___________________________________________);
}
五、分析简答题（10分）
1．（4分）试写出如图所示的二叉树分别按中序、后序遍历时得到的结点序列。
2. （6分）用序列（46，68，45，139，70，58，101，10，88，94）建立一个二叉排序树，画出该树，并求在等概率情况下查找成功的平均查找长度。
六、算法设计题（20分）
1、（8分）删除顺序表前i个元素。
已知顺序表的数据结构如下：
#define MaxSize 100
typedef struct
{
int data[MaxSize];
int last;
} SeqList;
使用如下函数原型：
bool fnDelete( SeqList *L, int i );
//成功删除则返回true，否则返回false
2、 (12分)假设二叉树采用左右孩子指针存储结构，即其结点数据类型描述为：
struct TreeNode{
int data;//数据域
struct TreeNode *left, *right;//指向其左右孩子结点
};
试编写一个函数，要在一棵树Tree中，找出最大值。函数原型如下：
bool fnGetMax( struct TreeNode *Tree, int *max );
//找到最大值则返回true，否则返回false;
2016年广东专插本华师上课辅导班招生简章
11月28开新的周末班，还有寒假班和冲刺班,有需要住宿的，可以提供校内宿舍，35元/晚,有热水器，空调等
分享到：
报名方式
1.直接来我校参观、报名。报名时带好身份证及正反面复印件2张、1寸蓝底彩照4张2寸蓝底彩照4张 。 （专升本在校生由学校开具证明，毕业生应交毕业证复印件）
2.学生选择网上或电话报名，学员可以电话、QQ、电子邮件报名或者索取招生简章，在指定时间内来校报到入学。
3.业余自考学生准备好个人资料和第一年学费，直接过来学校报名。
4.电话：020-85517608 或 13316047870 李老师(微信同号)
5.QQ：
6.广州招生网在线报名地址：点击进入网上报名系统
7.报名地址：广州天河中山大道西8号天河商贸大厦2203招生办(地铁3号线岗顶站；公交站师大暨大站)
（特别提醒：我校没有在各车站路口设立接待点，请广大考生自行来校，严防路人以指路带领为名上当受骗，中途勿受陌生人接待，以免误导，造成不必要的财产损失。）
