2018年4月高等教育自学考试全国统一命题考试
数据结构
（课程代码02331）
注意事项：
1．本试卷分为两部分，第一部分为选择题，第二部分为非选择题。
2．考生必须按试题顺序在答题卡（纸）指定位置上作答，答在试卷上无效。
3．涂写部分、画图部分必须使用2B铅笔，书写部分必须使用黑色字迹签字笔。
第一部分选择题
一、单项选择题：本大题共15小题，每小题2分，共30分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。
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．二维数组M，行下标取值范围为O～8，列下标取值范围为1～10，若按行优先存储时，元素M【8】【}5】的存储地址为ar，则按列优先存储时，地址ar存储的数组元素应是
A.M【8】【5】
B.M【5】【8】
C.M【3】【10】
D. M【0】【9】
7．根据二叉树的定义，3个结点构成的二叉树的树型有
A.2种B．3种 C.4种 D.5种
8．一棵有序树可转换为一棵二叉树，树的后序遍历对应二叉树的
A.前序遍历B．中序遍历C．后序遍历 D.以上都不对
9．若图G的邻接表中有奇数个表结点，则G是
A. 含奇数个顶点的图
B.无向图
C．含偶数个顶点的图 D.有向图
10. 若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑排序序列的结论是
A. 存在，且唯一B．存在，且不唯一
C．存在，可能不唯一 D. 无法确定是否存在
11.如果无向图G的最小生成树T中含有边(a，b)和(a，c)，则下列选项中，一定不在T中的边是
A.(b,c)
B.(b,d) c.(c,d) D.(c.e)
12.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上的是
A．插入排序B．希尔排序 C.归并排序 D.堆排序
13.若数据元素序列l1，13，15，7，8，9，23，2，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法是
A. 冒泡排序B．插入排序 C. 选择排序 D. 归并排序
14.线性表采用顺序存储或链式存储，对其进行查找的方法应是
A. 顺序查找B．二分查找 C. 散列查找 D. 索引查找
15.设有序表为{1,3，9，12, 32，41，45，62，75，77，82}，采用二分查找法查找关键字75，
查找过程中关键字之间的比较次数是
A.1 B．2 C．3 D.4
第二部分非选择题
二、填空题：本大题共10小题，每小题2分，共20分。
16.在数据结构中，从逻辑上可以把数据结构分为线性结构和____。
17.为便于实现单链表的插入及删除运算，需要在单链表中增加一个结点，该结点称为____。
18.在二维数组A【10】【8】中，每个数组元素占用4个存储单元，则数组A需要的存储单元个数是____。
19.对长度为1的广义表A，若有Head(A)=Tail(A)，则A=____。
20.设高为h的二叉树T中只有度为0和2的结点，则T包含的结点数最多为____。21．一个连通图的________是包含图中所有顶点的极小连通子图。
22.无向图G中含7个顶点，顶点间的边是随机设置的，为保证图G在任何情况下都是连通的，则需要的边数最少是____。
23.求单源最短路径的迪杰斯特拉（Dijkstra）算法是按照路径____不减的次序求出各条路径的。
24. 一组记录的关键字为(45，53，18，49，36，76，13，97，36，32)，利用快速排序方法对其进行排序，选择45为基准，一次划分后的结果为____。
25.对箱排序的改进和推广的排序算法是____。
三、解答题：本大题共4小题，每小题5分，共20分。
26．两个栈共享数组空间data[m]（定义如下），它们的栈底分别设在数组的两端（初始
化后top1=-1，top2=m）。
typedef struct {
DataType data[m];
int top1，top2;
} SeqStack;
回答下列问题。
(1)编写判断栈满的函数int stackfull(SeqStack *s)；
(2)编写进栈函数void push(SeqStack *s, int si，DataType x)，
其中，Si取值为0、1，分别表示栈底为0或m-1的栈。
27．已知二叉树T中含有元素A，B，C，D ,E，F，G, H，T的前序遍历序列、中序遍历序列和后序遍历序列如下，其中符号__表示未知元素。试写出①到⑩所代表的正确元素值。
前序遍历序列 A B D ① E F G ②
中序遍历序列③ B A ④ C G F ⑤
后序遍历序列⑥⑦⑧⑨H F C ⑩
28.设图G如题28图所示。
回答下列问题。
(1) 图G是否是有向无环图？
(2) 给出图G所有的拓扑排序序列。
29.设关键字序列为：53，15，72，52，48，67，63，23。己知散列表地址空间为0～11，散列函数为H (k)=k mod 11，采用线性探查再散列法解决冲突。．
(1) 将所给关键字数据依次填入该散列表中;
(2) 计算等概率下查找成功的平均查找长度。
四、算法阅读题：本大题共4小题，每小题5分．共20分。
30.已知队列的基本操作定义如下，请在空白处填写适当的语句，完成指定的功能。
#define QueueSize 100
typedefstruct{ //队列定义
char data[QueueSize];
int front, rear;
} CirQueue,
CirQueue Q;
void InitQueue( CirQueue *Q) //队列初始化
{ Q->front=Q->rear=0；
}
int QueueEmpty( CirQueue*Q) //判队列是否空
{ return____(1)____；
}
int QueueFull( CirQueue *Q) //判队列是否满
{ return (Q->rear+1)%QueueSize==Q->front;
}
char EnQueue( CirQueue *Q, char c) //入队操作
{ if( QueueFull(Q))
return '\0'; //操作失败
else
{ Q->data[Q->rear]=c；
Q->rear=____(2)____ ;
return c；//操作成功
}
char DeQueue(CirQueue*Q）//出队列操作
{ char x;
if(QueueEmpty(Q))
return'/n'; //操作失败
else
{ x=Q->data[Q-.front]；
Q->front=___(3)___;
return x; //操作成功
}
}
31.程序f31是将输入的m行n列的二维数组a变换为三元组表形式存储在数组b中。请在空白处填上适当内容将算法补充完整。
#dcfine MAXSIZE 100
typedefint DataType;
typedef struct {
int i,j //非零元素行列下标
Data Type v; //非零元素值
} TriTupleNode;
typedf struct{
TriTupleNode data[MAXSIZE] //存储三元组数组
int m,n,t；//m：矩阵的行，n：矩阵的列，t：非零元素数量} TSMatrix;
void f3l(TSMatrix *b, int *a, int m, int n)
//将m行n列的矩阵a变换为三元组表形式存储在b中
{ int i，j，k=0;
for (i=0; i for (j=0；j { if（*a!=0） { b->data[k].i=i； b->data[k].j =j; b->data[k].v=____(1)____; ____(2)____； } a++; } b->m=m; b->n=n； b->t=____(3)____； } 32.已知二叉树T如题32图所示。阅读程序f32，写出执行f32(T)的输出结果。typedef char DataType; typedef struct node { DataType data; //data是数据域 struct node * lchild,．rchild; //分别指向左右孩子 } BinTNode; typedef BinTNode * BinTree; void f32 ( BinTree bt ) { if(bt!=NULL) { f32 (bt->rchild); printf("%c", bt->data); f32 (bt->lchild); } } 执行结果： 33.阅读程序,写出执行结果。 void f33( int a[ ], int n ) { int i; for ( i=(n-1)/2; i>=0; 1-- ) Sift(a, i, n-1); } void Sift( int a[ ], int i, int h ) { int j, temp-a[i]; j=2*i+1; while (j <= h) { if(j j++； if( temp >= a[j] ) break; a[i]=a[j]; i=j; j=2*i+1 } a[i] = temp; } int main() { int i, a[10] = { 10, 20, 5, 23, 25, 62, 21, 1, 32, 9 }; f33( a, 10 ); for ( i=0; i<10; i++) printf("%d=",a[i]); printf("\n"); return 0; } 执行结果： 五、算法设计题：本题10分。 34．己知带有头结点的单链表定义如下： typedefstruct node { char ch; struct node *next; } ListNode; typedef ListNode* LinkList; 请编写函数int f34 ( LinkList h，char string[ ])，根据输入的字符串，建立不含重复字符的链表。 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素 一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表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; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。 2018 年10 月高等教育自学考试全国统一命题考试 C++程序设计试卷 ( 课程代码04737) 本试卷共l0 页，满分l00 分，考试时间l50 分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2．第一部分为选择题。必须对应试卷上的题号使用2B 铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5 毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题：本大题共20 小题，每小题l 分，共20 分。在每小题列出的备选项审只有 一项是最符合题目要求的，请将其选出。 2．设X 和y 均为bool 量，则x＆＆y 曲为真的条件是 A. 它们均为真 B ．其中一个为真 C. 它们均为假 D ．其中一个为假 3．拷贝构造函数应该是 A ．不带参数的构造函数 B ．带有一个参数的构造函数 C ．带有两个参数的构造函数 D ．缺省构造函数 4．以下说法中正确的是 A ．C++程序总是从第一个定义的函数开始执行 B ．C++程序总是从main 函数开始执行 C. C++ 中函数必须有返回值 D ．C++中函数名必须唯一 5．下列虚基类的声明中，正确的是 A ．class virtual B ：public A B ．class B ：virtual public A C ．class B ：public A virtual D ．virtual class B ：public A 6．下列哪个类型函数不适合声明为内联函数 A ．函数体语句较多 B ．函数体语句较少 C ．函数执行时间较短 D ．函数被频繁调用 7. 以下类模板定义正确的为 A ．template 一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1 C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆 2018年10月自考《公共关系学》真题 选择题部分 一、单项选择题:本大题共20小题，每小题1分，共20分。在每小题列出的备选项中只有一项是最符合题目要求的，请将其选出。 1、中国公关协会成立于 A. 1985 年 B. 1986 年 C. 1987 年 D. 1991 年 2、被称为公关理论发展史的第一个里程碑的著作是 A.公众舆论的形成 B.公共关系学 C.修辞学 D.高卢战论 3、《中国公共关系职业道德准则> 草拟及其实施方案》提出的时间是 A.1985 年 B.1986 年 C.1987 年 D. 1989 年 4、公关的功利意识指的是 A.形象意识 B.服务意识 C.沟通意识 D.互惠意识 5、横向展览会指的是 A.混合商品展览会 B.室内展览会 C.单一商品展览会 D.露天展览会 6、某银行举办存款突破亿元大关的庆祝活动，该活动属于 A.开幕庆典 B.周年庆典 C.重大成果庆典 D.特殊嘉奖庆典 7、“媒介是人体的延伸”的提出者是 A.巴勒克拉夫 B.麦克卢汉 C.拉斯韦尔 D.伯尼斯 8、人们希望归属于一个团体以得到关心、爱护、支持、友谊和忠诚，这种需要属于 A.生理需要 B.安全需要 C.社交需要 D.尊重需要 9、许多人竞相效仿某些有影响的特定人物的某种新奇行为而形成的社会风尚被称为 A.流行 B.流言 C.舆论 D.风俗 10、那些能够对信息的提供、制作、编辑和报道采取“疏导”与“抑制”行为的关键人物为A.策划人B.创意人 C.把关人 D.监督人 11、公关策划全过程的首要环节是 A.确定目标 B.设计方案 C.选择方案 D.实施方案 12、个人不愿意因为与众不同而感到孤立，从而放弃自己的意见的“随大流”行为是 A.自我评价行为 B.社会逆反行为 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 A． 11 B.35 C. 19 D. 53 图一 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F D. B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) 数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 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; 3.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为 2018年10月高等教育自学考试全国统一命题考试 C++程序设计试卷 (课程代码04737) 本试卷共l0页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题：本大题共20小题，每小题l分，共20分。在每小题列出的备选项审只有 一项是最符合题目要求的，请将其选出。 2．设X和y均为bool量，则x＆＆y曲为真的条件是 A.它们均为真 B．其中一个为真 C.它们均为假 D．其中一个为假 3．拷贝构造函数应该是 A．不带参数的构造函数 B．带有一个参数的构造函数 C．带有两个参数的构造函数 D．缺省构造函数 4．以下说法中正确的是 A．C++程序总是从第一个定义的函数开始执行 B．C++程序总是从main函数开始执行 C. C++中函数必须有返回值 D．C++中函数名必须唯一 5．下列虚基类的声明中，正确的是 A．class virtual B：public A B．class B：virtual public A C．class B：public A virtual D．virtual class B：public A 6．下列哪个类型函数不适合声明为内联函数 A．函数体语句较多 B．函数体语句较少 C．函数执行时间较短 D．函数被频繁调用 7.以下类模板定义正确的为 A．template 一．选择题（每小题1分，共8分） 1.设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主存储，a[0][0]的存储地址为100，每个元素占1个地址空间，则a[3][2]的地址为（）。 （A）102 （B）105 （C）106 （D）108 2.森林转换为二叉树后，从根结点开始一直沿着右子数下去，一共有4个结点，表明（）。 （A）森林有4棵树（B）森林的最大深度为4 （C）森林的第一棵树有4层（D）森林有4个结点 3.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）。 （A）e （B）2e （C）n^2－e （D）n^2－2e 4.在内部排序中，排序时不稳定的有（）。 （A）插入排序（B）冒泡排序（C）快速排序（D）归并排序 5.设一数列的顺序为1，2，3，4，5，通过栈结构不可能派成的顺序数列为（）。 （A）3，2，5，4，1 （B）1，5，4，2，3 （C）2，4，3，5，1 （D）4，5，3，2，1 6.一个n条边的连通无向图，其顶点的个数至多为（）。 （A）n－１（B）n（C）n＋１（Ｄ）nlog2n 7.总共3层的完全二叉树，其结点数至少有（）个。 （A）3 （B）4 （C）7 （D）8 8.已知某算法的执行时间为（n^3+n^2+n）log2（n+2），n为问题规模，则该算法的时间复杂度是（）。 （A）O（n）（B）O（n^2） （C）O（log2n）（D）O（n^3log2n） 二．判断题（每题1分，共8分。正确的打√，错误的打×） 1.只要是算法，肯定可以在有限的时间内完成。（） 2.无论是线性表还是树，每一个结点的直接前驱结点最多只有一个。（） 3.不论是行优先还是列优先，二维数组的最后一个元素的存储位置是一样的。（） 4.直接插入排序时，关键码的比较次数与记录的初始排列无关。（） 5.二叉树的先序遍历不可能与中序遍历相同。（） 6.任何一棵二叉树，不可能没有叶子结点。（） 7.一个稀疏矩阵采用三元组法存储不可能是（5，3，7），（5，4，4），（5，3，5）。（） 8.一个无序的顺序表不能采用折半查找法进行查找。（）。 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 2018年4月高等教育自学考试《英语（一）》试题 课程代码：00012 一、阅读判断 Finding Paradise (天堂) and Success in Retirement Ivy Singh and her husband had their retirement all planned out. They wanted to have a place with enough land to grow plants. The couple successfully found a proper place and turned it into a farm called Bollywood Veggies. "We came and had a look and we found paradise. We started Bollywood Veggies there and then," she says. The basic idea of starting the farm was to keep themselves busy in retirement. Mrs. Singh says it was never begun as a business. "We started this as a lifestyle project for retirement." The farm's produce includes beans, cabbage and other crops. Soon, more people found out about the farm. Visitors often asked whether the farm offered any food or drinks. So the couple started a restaurant and a food museum on the farm. As the farm changed from a retirement to a commercial project, Mrs. Singh sought new business opportunities. A key area was growing bananas. Given the popularity of bananas and their use in a range of food products, she saw great potential. The farm uses its crop to make products such as banana chips and bread. Mrs. Singh, driven by the success of the project, now wants to open a retirement home on the farm. She says the farm is a nice place for people who have retired. Mrs. Singh says she does not care much about the profit, because she is getting to live her dream while making a difference to society. 1. Ivy and her husband made a careful plan for retirement. A. True B. False C. Not Given 2. Before retirement, the couple were doing business on plants. A. True B. False C. Not Given 3. The couple started Bollywood Veggies for business purposes. A. True B. False C. Not Given 4. Cabbage was the first vegetable planted on the farm. A. True B. False C. Not Given 5. The couple opened a restaurant close to the farm. A. True B. False C. Not Given 6. Mrs. Singh planted bananas because they were very popular. A. True B. False C. Not Given 7. Visitors to the farm like its banana chips the best. A. True B. False C. Not Given 8. Mrs. Singh built a retirement home on the farm. A. True B. False C. Not Given 9. Mrs. Singh thinks the farm is a good place for retired people. 学习-----好资料 数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后 2018年近代史自考试题及答案简答题: 1、试析英国资产阶级革命爆发的原因。 （一）经济基础——资本主义经济的兴起和发展，它是英国资产阶级革命爆发的最基础的条件。具体表现在以下几个方面： a.新航路开辟后，英国成为大西洋航路的中心，便利了英国的海外贸易和掠夺。 b.海外贸易的拓展，推动了英国工业革命的发展，手工工场在制呢、采煤、炼铁、造船等领域建立并得到发展。 c.随着制呢业的发展，“圈地运动”愈演愈烈，英国农村出现许多的资本主义牧场和农场，同时出现农业工人。在英国，资本主义已深入农村。 （二）阶级基础——资产阶级和新贵族的形成，他们是英国资产阶级革命的主要推动者和领导阶级，是资产阶级革命运动兴起的必要条件。 海外贸易和掠夺的进行，圈地运动的发展，使英国的银行家、大商人和手工工场主积累了大量的资本，逐渐形成新兴的资产阶级。在农村经营农场和牧场的农场主和牧场主，有的也经营工商业，他们成为新贵族，同其他资产阶级分子有着共同额利益。 （三）客观条件——海上霸权的确立 16世纪统治英国的都铎王朝在竭力削弱旧贵族的势力，同时鼓励工商业和海外掠夺，打败了老牌的殖民强国西班牙，建立了海上霸权，这一切客观上有利于资本主义的发展。 （四）根本原因——封建制度严重阻碍了资本主义经济的发展 随着英国资本主义的发展，封建专制统治和资本主义发展的矛盾，成为英国社会的根本矛盾，它们矛盾的不断激化，最终成为英国资产阶级革命的根本原因。 （五）直接原因——封建王朝专制统治导致阶级矛盾的激化 17世纪，斯图亚特王朝厉行专制，经常触犯到资产阶级的利益。又实行宗教专制，迫害“清教徒”。导致阶级矛盾激化。 （六）思想基础——清教运动 宗教改革后，英国国教在英国确立统治地位，清教运动主要目的是清除国教中的天主教残余，这与资产阶级的反封建斗争有非常多的共同要求，这一时期的 第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 2018年自考《外科学》试题及答案 01、化脓性关节炎与关节结核的鉴别，下列哪项无价值【D】 A、是否有高热等急性全身表现 B、局部是否有红肿、疼痛与皮温明显增高 C、血和关节液的白细胞总数和中性粒细胞增多的程度 D、浮髌试验阳性 E、关节液是否培养出革兰氏阳性球菌 02、急性血源性骨髓炎早期局部穿刺的正确方法是【C】 A、一次穿入骨髓腔 B、一次穿入骨膜下 C、逐层穿刺 D、不可穿入骨髓内 E、仅刺入软组织即可 03、骨关节结核最常见的发生部位，是【B】 A、全身滑膜面积最大的膝关节 B、脊柱椎体 C、活动最多的髋关节 D、负重最大的踝关节 E、肌肉最不发达的腕关节 04、临床诊断脊柱结核，下列哪项指标最有价值【B】 A、局部疼痛肿胀 B、X线摄片 C、穿刺液作结核菌培养 D、消瘦、贫血、盗汗及食欲不振 E、结核菌素试验 05、X线片上成人的椎体结核和椎体肿瘤的主要鉴别点，是【D】 A、椎体的破坏程度 B、是否有死骨形成 C、椎旁软组织阴影 D、椎间隙是否狭窄或消失 E、椎体骨质疏松的程度 06、骨关节结核下列哪种情况，不适于手术治疗【D】 A、有明显死骨，较大脓肿 B、经久不愈的窦道 C、脊柱结核合并截瘫 D、全身中毒症状严重，衰弱，重度贫血 E、早期全关节结核，为了抢救关节功能 07、诊断成人脊柱结核最可靠的依据是【D】 A、有低热，盗汗史 B、血沉快 C、结核菌素试验(+) D、X线摄片示椎间隙狭窄，相邻椎体边缘模糊 E、全身虚弱、贫血 08、在治疗早期膝关节滑膜结核中，除全身治疗外，局部治疗最 恰当的措施是【C】 A、制动 B、穿刺抽脓，注入抗痨药 C、穿刺抽脓，注入抗痨药+制动 D、滑膜切除术 E、膝关节加压融合术 09、单纯滑膜结核的X线表现是【C】 A、关节间隙狭窄，软组织肿胀 B、关节间隙增宽，骨质破坏 C、骨质疏松，软组织肿胀 D、骨质密度增高 E、骨膜反应性增生 10、早期滑膜结核与类风湿性关节炎鉴别的可靠依据是【E】 A、累及关节的数目 B、血沉是否正常 C、关节间隙是否狭窄 D、结核菌素试验 E、滑膜组织病理学检查 11、全关节结核是指【E】 A、关节内积液增多 B、X线片可见骨质破坏 C、血沉明显增快 四川大学 《数据结构与算法分析》课程 考试模拟试卷 模拟试卷一 一、单选题（每题2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成 ( )个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左孩 子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有双 亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};数据结构模拟试题及答案
数据结构试题及答案(免费)
2018年10月自考04737C 真题及答案(20190417175937)
数据结构模拟试题1
2018年10月自考《公共关系学》真题【自考真题】
《数据结构》模拟试卷一及答案
数据结构试题及答案
2018年10月自考04737 C++真题及答案
数据结构模拟试题9
数据结构习题与答案
2018年4月自考 英语(一) 试题
数据结构模拟试题一及答案汇编
2018年近代史自考试题及答案
数据结构试题及答案
2018年自考《外科学》试题及答案
数据结构与算法模拟试卷一、二及参考答案
相关主题
文本预览