韩山师范学院专升本插班生考试样卷
计算机科学与技术专业数据结构样卷
一、单项选择题（每题2分，共40分）。
1.关于线性表的描述，错误的是（）。
A. 线性表是线性结构
B. 线性表就是单链表
C. 线性表的顺序存储结构，必须占用一片连续的存储单元
D. 线性表的链式存储结构，不必占用连续的存储单元
2.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储( )。
A.数据的处理方法
B.数据元素的类型
C.数据元素之间的关系
D.数据的存储方法
3.与单链表相比，双链表的优点之一是( )。
A.插入、删除操作更简单
B.可以进行随机访问
C.可以省略表头指针或表尾指针
D.顺序访问相邻结点更灵活
4. 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为( )。
A. n+1
B. n
C. n-1
D. n(n-1)/2
5．如果结点A有3个兄弟，而且B为A的双亲，则B是度为（）
A．3 B．4 C．5 D．1
6．在具有N个单元的顺序存储循环队列中，假定front和rear分别为队头
指针和队尾指针，则判断队满的条件为（）。
A．front == rear B．(rear+1) % MAXSIZE == front
C．front - rear==1 D．rear % MAXSIZE == front
7. 某二叉树的前序遍历序列为 ABDGCEFH ，中序遍历序列为 DGBAECHF ，则后序遍历序列为（）。
A. BDGCEFHA
B. GDBECFHA
C. BDGAECHF
D. GDBEHFCA
8．设无向图的顶点个数为n，则该图最多有（）条边。
A. n-1
B. n(n-1)/2 C．n(n+1)/2 D. 0
9. 在一个长度为N的线性表中顺序查找值为x的元素时，在等概率的情况下查找成功时的平均查找长度为（）。
A. N
B. N/2
C. (N+1)/2
D. (N-1)/2
10．深度为5的二叉树至多有( )个结点。
A.16
B.32
C.31
D.10
11. 堆的形状是一棵( )。
A. 二叉排序树
B.满二叉树
C. 完全二叉树
D. 平衡二叉树
12．下列关于数据结构的叙述中，正确的是( )。
A. 数组是同类型值的集合
B. 树是一种线性结构
C. 递归算法的程序结构比迭代算法的程序结构更为精炼
D. 用一维数组存储二叉树，总是以先序遍历的顺序存储各结点
13. 在具有 n(n>1) 个结点的完全二叉树中，结点 i(2*i>n) 的左孩子结点是（）。
A. 2*i
B. 2*i+1
C. 不存在
D. 2*i-1
14. 在有n个结点的二叉树中，值为非空的链域的个数为( )。
A. n-1
B. 2*n-1
C. n+1
D. 2*n+1
15. 若对一个已排好序的序列进行排序，在下列四种方法中，哪种比较好（）。
A. 冒泡法
B. 直接选择法
C. 直接插入法
D. 归并法
16. 设单链表中指针p指向结点A，若A的后继结点存在，则删除该后继结
点需要修改指针的操作为（）。
A．p->next=p->next->next B．p=p->next
C．p=p->next->next D．p->next=p
17. 队列操作的原则是( )。
A. 先进先出
B. 后进先出
C. 只能进行插入
D. 只能进行删除
18. 对树进行层次遍历时，通常是采用( )作为辅助来实现算法的。A．栈 B. 队列 C. 树 D. 图
19. ( )是顺序存储方式的优点。
A. 存储密度大
B. 插入运算方便
C. 删除运算方便
D. 可方便地用于各种逻辑结构的存储表示
20. 数组A[5][6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为( )。
A. 1140
B. 1145
C. 1120
D. 1125
二、判断题（每题1分，共10分）。
以下各种说法，你认为对的在前面括号打√，错误的打×。
( )1．队列只能采用链式存储方式。
( )2.二叉树的度一定是2。
( )3.线性结构也是一种树结构。
( )4.有向图用邻接表表示后，顶点i的入度等于该顶点对应的单链表的元素个数。
( )5．满二叉树一定有偶数个结点。
( )6．直接插入排序的关键码比较次数与初始排列有关。
( )7．顺序存储方式只能用于存储线性结构。
( )8. 给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )9．在对链队列作出队操作时，不会改变front指针的值。
( )10. 堆排序是不稳定排序。
三、填空题（每空2分，共18分）。
1．中缀算式（3+4）*2 /（8-5）所对应的后缀算式为______ __。
2. 某算法的时间复杂度为(5*n2+1000*n*log
n+4*n-8)/(10*n)，其数量级表
2
示为______________。
3. 用1000个结点构造的二叉树，最少___________层，最多__________层。
4. 假定一个线性表为(12,23,74,55,63,40,82,36)，若按Key % 3条件进行划分，使得同一余数的元素成为一个子表，则得到的三个子表分别为____________________、___________________和_____________________。
5. 假定一棵二叉树广义表表示为a(b(c),d(e,f))，其中序遍历序列为____________________，层次遍历序列为_____________________。
四、程序填空题（每个语句2分，共12分）
1．下面是向以BST为树根指针的二叉搜索树上插入值为item的结点的递归算法。请将缺失语句填上。
void Insert(BTreeNode*& BST, const ElemType& item)
{
if( BST == NULL ) {
BTreeNode* p = new BTreeNode;
p->data = item;
_______________________;
BST = p;
}
else if( item < BST->data ) ___________________;
else ________________________;
}
2．下面是向单链表的末尾添加一个元素的算法。请将缺失的语句填上。Void InsertRear( LNode*& HL, const ElemType& item )
{ LNode* newptr;
newptr = new LNode;
if ( newptr == NULL ){
cerr << "Memory allocation failare!" << endl;
exit( 1 );
}
newptr->data = item;
_________________
if ( HL == NULL ) HL = newptr;
else{
____________________;
while ( ) p = p->next;
p->next = newptr;
}
}
五、算法设计题（20分）
1．编写算法函数，把顺序表List原地置逆。(10分)
顺序表的数据结构如下：
typedef struct{
int data[100];
int last;//最后元素的下标
} SeqList;
函数原形为：void fnReverse( SeqList &List );
2.二叉树采用左右孩子指针存储结构：
Struct TreeNode{
Int data;//数据域
Struct TreeNode *left, *right;//指向其左右孩子结点
};
请编写一个递归函数，要在一棵树T中，找出值是x的结点的兄弟结点。(10分) 函数原形如下：
Struct TreeNode *fnGetBrother( Struct TreeNode *T, int x );
《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■
2017年韩山师范学院本科插班生考试试卷 计算机科学与技术专业高级语言程序设计试卷（A卷） 一、填空题（每空1分，共10分） 1．一个C程序的执行是从本程序的函数开始。 2．结构化程序的三种基本结构为顺序结构、_________________、_________________。 3．能表示“整型变量x的绝对值小于5”的C语言表达式是________________ (不得使用系统函数)。 4．在C语言中，当表达式值为0时表示逻辑值“假”，当表达式值为________________时表示逻辑值“真”。 5．在位运算中，操作数每左移一位（无溢出），其结果相当于操作数____________以2。 6．设有定义FILE *fp; 则关闭fp对应文件的操作语句是。 7．在C程序中，根据数据的组织形式可以可分为___________文件和___________文件。 8．若有定义char s[]="\n123\\"; 则strlen(s)的值为_______；sizeof(s) 的值为_______。 二、单项选择题（每小题1.5分，共30分） 1．C语言中的标识符只能由字母、数字和下划线，且第一个字符( )。A.必须为字母 B.必须为下划线 C.必须为字母或下划线 D. 可以是字母或数字或下划线 2．设a，b为整型变量，以下合法的表达式为( )。
A. b=a/2 B. b=*a+2 C. b+a=2 D. b=a%2.5 3．以下选项中能表示合法常量的是 A．整数：1,200 B．实数：1.5E2.0 C．字符斜杠：'\' D．字符串："\007" 4．若有a=4,b=3,c=5,则表达式a
实验一线性表的顺序存储实验 一、实验目的 1、掌握用Visual C++6.0上机调试顺序表的基本方法 2、掌握顺序表的基本操作，插入、删除、查找等算法的实现 二、实验内容 1、顺序表基本操作的实现 [问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 [基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 实验二单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p
指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。 [基本要求]用链式存储结构实现存储 [实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。 2、求表长以及有序单链表的合并算法的实现 [问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。 [基本要求]用链式存储结构实现存储 实验三栈的实现及应用 一、实验目的 1、掌握顺序栈的类型定义方法。 2、掌握在顺序栈上实现的六种基本算法。 2、掌握顺序栈的简单应用。 二、实验内容
数据结构试题样题及答案 一、单项选择题（每小题2分，共30分） 1.数据结构中，与所使用的计算机无关的是数据的（）结构。 A. 逻辑 B. 物理 C. 存储 D. 逻辑与物理 2.下述各类表中可以随机访问的是（）。 A. 单向链表 B. 双向链表 C.单向循环链表 D.顺序表 3.在一个长度为n的顺序表中为了删除第5个元素，从前到后依次移动了15个元素。则原顺序表的长度为（）。 A. 21 B. 20 C. 19 D. 25 4.元素2，4，6按顺序依次进栈，则该栈的不可能的输出序列是（）。 A. 6 4 2 B. 6 2 4 C. 4 2 6 D. 2 6 4 5.一个队列的入队序列是5，6，7，8，则队列的输出序列是（）。 A. 5 6 7 8 B. 8 7 6 5 C. 7 8 6 5 D.可能有多种情况 6. 串函数StrCmp（“d”，“D”）的值为（）。 A．0 B．1 C．-1 D．3 7．在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 A．p=q→next B．p→next=q C．p→next=q→next D．q→next=NULL 8.设一棵哈夫曼树共有n个非叶结点，则该树一共有（）个结点。 A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1) 9.对如图1所示二叉树进行中序遍历，结果是（）。 A. dfebagc B. defbagc C. defbacg D.dbaefcg 图1 10 . 任何一个无向连通图的最小生成树（）。 A.至少有一棵 B.只有一棵 C.一定有多棵 D.可能不存在 11．设有一个10阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素A8,5在一维数组B中的下标是（）。 A．33 B．32 C．85 D．41 12 .一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。 A．31，29，37，85，47，70 B．29，31，37，47，70，85
《数据结构》期末考试试卷样卷 成绩＿＿＿＿＿＿＿＿ 一、单项选择题：（每题2分，共30分） 1、以下说法正确的是（）。 A. 数据元素是数据的最小单位 B. 数据项是数据的基本单位 C. 数据结构是带有结构的各数据项的集合 D. 一些表面上很不相同的数据可以有相同的逻辑结构 2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。 A. 存储结构 B. 存储实现 C. 逻辑结构 D. 运算实现 3、判断一个队列QU（最多元素为m0）为满队的条件是（）。 A. QU->rear-QU->front==m0 B. QU->rear-QU->front-1==m0 C. QU->rear==QU->front D. QU->front==QU->rear+1 4、给定n个数据元素，建立对应的有序单链表的时间复杂度是（）。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 5、一个非空广义表的表头（）。 A. 不可能是子表 B. 只能是子表 C. 原子或子表均可 D. 只能是原子 6、设完全二叉树中拥有65 个结点，则其深度为（）。 A. 5 B. 6 C. 7 D. 8 7、根据二叉树的（），可以唯一确定该二叉树的形态。 A. 先序和中序序列 B. 先序和后序序列 C. 中序和后序序列 D. 先序和层序序列 8、若广义表A满足Head(A)=Tail(A)，则A为（）。 A. () B. (()) C. ((),()) D. ((),(),()) 9、下面不正确的说法是（）。 (1)在AOE网中，减少任一关键活动上的权值后，整个工期也就相应减小； (2)AOE网工程的工期为关键活动上的权值之和； (3)在关键路径上的活动都是关键活动，而关键活动也必定在关键路径上。 A. (1) B. (2) C. (3) D. (1) 、(2) 10、图的深度优先遍历算法分别类似于二叉树的（）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 层序遍历 11、从图的邻接矩阵中，容易确定（）。 A. 主对角线的元素全部为1 B. 主对角线的元素不全为0 C. 任意两个顶点之间是否关联 D. 是否为一个连通图 12、顺序查找适用于存储结构为（）的线性表。 A. 散列存储 B. 压缩存储 C. 顺序存储或链式存储 D. 索引存储 13、从具有n个结点的二叉排序树中查找一个元素时，最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 14、在关键字随机分布的情况下，用二叉排序树进行查找，其查找长度与（）量级相当。 A. 顺序查找 B. 折半查找 C. 分块查找 D. 均不是 15、一组记录的关键字序列为{46,79,56,38,40,84}，利用快速排序方法，以第一个记录为基准得到的一次划分是（）。 A. 38,40,46,56,79,84 B. 40,38,46,79,56,84 C. 40,38,46,56,79,84 D. 40,38,46,84,56,79 - 1 -
韩山师范学院专升本插班生考试样卷 计算机科学与技术专业高级语言程序设计样卷 一、填空题（每空1分，共10分） 1.C语言的数据类型中，构造类型包括：数组、和。 2.在C程序中，指针变量能够赋值或值。 3.C目标程序经后生成扩展名为exe的可执行程序文件。 4.设有定义语句 static char s[5」；则s[4]的值是。 5.设x为int型变量。与逻辑表达式!x等价的关系表达式是。 6.若一全局变量只允许本程序文件中的函数使用，则该变量需要使用的存 储类别是。 7.磁盘文件按文件读写方式分类可以为顺序存取文件和。 8.设有下列结构体变量xx的定义，则表达式sizeof(xx)的值是 _________。 struct { long num; char name[20]; union{float y; short z;} yz; ｝xx; 二、单项选择题（每小题1.5分，共30分）
1.设有定义int x=8, y, z; 则执行y=z=x++, x=y= =z; 语句后，变量x 值是( ) A、0 B、1 C、8 D、9 2.有以下程序 main( ) { int i=1,j=1,k=2; if((j++‖k++)&&i++) printf("%d,%d,%d\n",i,j,k);} 执行后输出结果是( ) A、 1,1,2 B、2,2,1 C、 2,2,2 D、2,2,3 3.已知i、j、k为int型变量，若从键盘输入：1，2，3<回车>，使i的 值为1、j的值为2、k的值为3，以下选项中正确的输入语句是( ) A、scanf( “%2d%2d%2d”,&i,&j,&k); B、scanf( “%d %d %d”,&i,&j,&k); C、scanf( “%d,%d,%d”,&i,&j,&k); D、scanf( “i=%d,j=%d,k=%d”,&i,&j,&k); 4.有以下程序 main() { int a=5,b=4,c=3,d=2; if(a>b>c) printf("%d\n",d); else if((c-1>=d)= =1) printf("%d\n",d+1); else printf("%d\n",d+2); } 执行后输出结果是 ( ) A、2 B、3 C、 4 D、编译时有错，无结果 5.以下程序段 ( ) x=1; do { x=x*x;} while (!x);
数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在 676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 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.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二 分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 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 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
数据结构试卷（五） 一、选择题(30分) 1．数据的最小单位是（）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。 (A) 40，50，20，95 (B) 15，40，60，20 (C) 15，20，40，45 (D) 45，40，15，20 3．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。 (A) 15，25，35，50，20，40，80，85，36，70 (B) 15，25，35，50，80，20，85，40，70，36 (C) 15，25，35，50，80，85，20，36，40，70 (D) 15，25，35，50，80，20，36，40，70，85 4．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。 (A) “STRUCTURE”(B) “DATA” (C) “ASTRUCTUR”(D) “DATASTRUCTURE” 5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。 (A) O(log2n) (B) O(1) (C) O(n2) (D) O(n) 6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为N l，……，度数为m的结点数为Nm，则N0=（）。 (A) N l+N2+……+Nm (B) l+N2+2N3+3N4+……+(m-1)Nm (C) N2+2N3+3N4+……+(m-1)Nm (D) 2N l+3N2+……+(m+1)Nm 7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 (A) 25 (B) 10 (C) 7 (D) 1 8．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。 (A) abedfc (B) acfebd (C) aebdfc (D) aedfcb 9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。 (A) n-i (B) n-1-i (C) n+1-i (D) 不能确定 10 设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45 为基准而得到一趟快速排序的结果是（）。 (A) 40，42，45，55，80，83 (B) 42，40，45，80，85，88 (C) 42，40，45，55，80，85 (D) 42，40，45，85，55，80 二、填空题(共30分) 1.设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶 指针top2的初值为n，则判断共享栈满的条件是____________________。 2.在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。
考场： 座位号： 专业名称： 装订线 装订线 装订线 广州大学华软软件学院第 20XX-20XX 学年第 X 学期考试卷 课程代码： SS1005 课程名称： 数据结构与算法 考试时间： 90 分钟 考试形式： 闭卷 试卷类型： A 学分： 4 一、 单项选择题（共15小题，每小题2分，共30分）在每小题列出的 选项中只有一个选项符合题目要求，将正确选项前的字母填写在答题纸上。 1. 数据三种最主要的逻辑结构是树形结构和（ ）。 A. 线性表、二叉树 B. 线性结构、图状结构 C. 线性表、图 D. 树形结构、堆 2. 以下数据结构中，（ ）是线性数据结构。 A ．树 B ．图 C ．堆 D ．栈 3. 下面关于线性表的叙述中，错误的是哪一个？（ ） A ．若线性表采用顺序存储结构，则必须占用一片连续的存储单元。 B ．若线性表采用顺序存储结构，则便于进行插入和删除操作。 C ．若线性表采用链接存储结构，则不必占用一片连续的存储单元。 D ．若线性表采用链接存储结构，则便于插入和删除操作。 4. p 是指向单链表头结点的指针，若该链表是空表，下面正确的说法是( )。 A. p = = NULL B. p != NULL C. p->next = =NULL D. p->next = =NULL
5.在指针p指向单链表结点之后插入s所指结点的操作是：（）。 A．p->next=s; B．s->next=p->next ;p->next=s; C．s->next=p; D．s->next=p->next; 6.存取数据时采用先进先出的原则的数据结构是（）。 A.队列 B.栈 C.字符串 D.线性表 7.假定栈用单链表的存储结构表示，栈的栈顶指针为top，当结点x入栈时执行的 操作为( )。 A.x->next=top; B. top->next=x; top=x; C. top=x; D. x->next=top; top=x; 8.队列的数据出队操作在（）进行。 A.队尾位置 B.队头位置 C. 任意位置 D. 中间位置 9.树的度是指（）。 A.树的结点数 B.树的后继个数 C. 树中任一结点最大的后继数 D. 以上都不是 10.具有8个叶子结点的二叉树中有（）个双支结点。 A．7 B．8 C．9 D．10 11.下面对完全二叉树描述正确的是（）。 A.所有层的结点数都必须是满的 B.除最后一层，其它层上的结点数都必须 是满的 C.最后一层的结点数不能是满的 D.以上都不是 12.将100个元素散列到10000个单元的散列表中，则（）产生冲突。 A.一定会 B. 一定不会 C. 仍可能会 13.假定利用数组a表示一个栈，用top 保存栈顶位置，top=-1表示栈空，已知栈 中有数据，当元素x进栈时的操作为（）。 A.a[--top]=x; B.a[top--]=x; C. a[++top]=x; D. a[top++]=x; 14.n个顶点的无向图，至多有（）条边。 A．n-l B．n(n-1)/2 C．n(n+l) D．2n 15.无向图G=(V,E),其中：V={a,b,c,d }, E={(a,b), (a,c),(b,d),(c,d)}，对该 图进行广度优先遍历，得到的顶点序列正确的是（）。 A．a,c,b,d B．a,d,c,b C．a,c,d,b D．a,b,d,c 第 2 页共4 页
数据结构09 一. 填空题（26分，每空2分） 1. 声明抽象数据类型的目的是________________________________________。 2. 已知结点类Node
韩山师范学院2016届毕业生就业质量年度报告 第一部分学校情况 韩山师范学院是一所历史悠久、特色鲜明的广东省属本科师范院校，位于享有“中国瓷都”美誉的国家历史文化名城潮州市，校园占地面积达74万平方米，建筑面积51.8万平方米，依山傍水，环境优美，景色怡人，设施齐全，是读书治学和工作生活的理想园地。 学校设有文学与新闻传播学院等16个二级学院，72个本科专业（含方向），涵盖文学、历史学、法学、教育学、理学、工学、管理学、艺术学8个学科门类和基础教育的所有学科。建有国家级特色专业3个、省级15个，国家级专业综合改革试点1个、省级6个，省级人才培养模式创新实验区2个，省级重点学科2个、省级协同育人平台1个，省级精品课程和优质课程13门。学校面向全国十六个省（区）和港澳招生，全日制在校生17500多人。 学校重视学生科学人文素养、实践能力和创新精神的培养。近两年来，学生在参加全国和省级各类比赛如“挑战杯”大学生课外科技作品竞赛、数学建模竞赛、电子设计大赛、机器人大赛和师范生教育教学技能竞赛中屡获佳绩，其中国家级40多项，省级200多项。如在第八届“挑战杯”复星中国大学生创业计划竞赛中，我校代表队与清华大学、复旦大学、同济大学等名牌高校同台竞技，以出色的表现赢得了大赛金奖。学生的核心竞争力不断提升，2010年以来，毕业生总体就业率达94%以上，居省内高校前列。 学校坚持开放办学，积极拓展国际化发展路径，先后与哈萨克斯坦、韩国、日本、马来西亚、澳大利亚、美国、英国、乌克兰等十多个国家，以及港澳台地区的20多所高校和教育机构建立了密切的教育与学术交流合作关系，扩大了办学领域，提升了学校办学的国际化水平和对外影响力。 学校坚持“师范性、地方性、应用性”办学定位，秉持创新、协调、绿色、开放、共享的发展理念，深化教育教学改革，全面推进“创新强校工程”，努力把我校建设成为既符合应用型大学标准，又具有鲜明办学特色、较高知名度和较大影响力的应用型本科院校。
数据结构试卷 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（） A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3个程序段，第一程序段的执行次数为错误!未找到引用源。，第二个程序段执行次数为4n，第三个程序段的执行次数为0.06错误!未找到引用源。，则该算法的时间复杂度为（）。 A．O（n）B．O（错误!未找到引用源。）C．O（错误!未找到引用源。）D．O （错误!未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={
数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散
韩山师范学院2017年本科插班生考试试卷 计算机科学与技术 专业 数据结构 试卷（A 卷） 一、单项选择题（每题2分，共30分） 1. 对线性表，在下列哪种情况下应当采用链表表示？( ) A. 经常需要随机地存取元素 B. 经常需要进行插入和删除操作 C. 表中元素需要占据一片连续的存储空间 D. 表中元素的个数不变 2. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( )。 A. 2 3 B. 3 2 1 C. 3 1 2 D. 1 2 3 3．程序段s=i=0；do {i=i+1； s=s+i ；}while(i<=n)；的时间复杂度为（ ）。 A. O(n) B. O(nlog 2n) C.O(n 2) D.O(n 3/2) 4．一个非空广义表的表头（ ）。 A.不可能是子表 B.只能是子表 C.只能是原子 D.可以是子表或原子 5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ）。 A. front=front+1 B. front=(front+1)%(m-1) C. front=(front-1)%m D. front=(front+1)%m 6．在一个单链表中,若q 所指结点是p 所指结点的前驱结点,若在q 与p 之间插入一个s 所指的结点,则执行( )。 A. s →link=p →link; p →link=s; B. p →link=s; s →link=q; C. q →link=s; s →link =p; D. p →link=s →link; s →link=p;
《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i《数据结构》期末考试试卷
相关主题
文本预览