1、数据结构导论自考题模拟 11及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.逻辑关系是指数据元素的_（分数：2.00）A.存储方式B.数据项C.结构D.关联方式2.算法能正确地实现预定功能的特性称为_（分数：2.00）A.正确性B.易读性C.健壮性D.时空性3.for(i=0;in;i+) for(j=0;jn;j+) Aij=i*j; 上面算法的时间复杂度为_ A.O(1) B.O(n2) C.O(log2n) D.O(n)（分数：2.00）A.B.C.D.4.带头结点的单链表 head为空的判断条件为_（分数：2.00）A.head
2、=NULLB.head!=NULLC.head-next=NULLD.head-next=head5.设顺序表有 10个元素，则在第 4个元素前插入一个元素所需移动元素的个数为_（分数：2.00）A.6B.7C.8D.96.已知一个单链表中，指针 q指向指针 p的前驱结点，若在指针 q所指结点和指针 p所指结点之间插入指针 s所指结点，则需执行_（分数：2.00）A.q-next=s;p-next=s;B.q-next=s;s-next=q;C.q-next=s;q-next=p;D.q-next=s;s-next=p;7.循环链表中一个结点有多少个指针_（分数：2.00）A.1B.2C.3D
3、.08.设指针 p指向循环链表的某一结点，则双链表结构的对称性可用哪项来刻画_（分数：2.00）A.p-prior-next=p-next-nextB.p-prior-next=p-next-priorC.p-prior-prior=p-next-priorD.p-next-next=p-prior-prior9.一个栈的入栈序列是 a、b、c、d、e，则栈的可能的输出序列是_（分数：2.00）A.cdabeB.decbaC.cabdeD.dabec10.设栈 S和队列 Q的初始状态为空，元素 e 1 ，e 2 ，e 3 ，e 4 ，e 5 和 e 6 依次通过栈 S，元素退栈后即进入队列 Q
4、，若 6个元素的出队序列是 e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈 S的容量至少为_（分数：2.00）A.5B.2C.4D.311.顺序队列的入队列操作应为_（分数：2.00）A.SQ.dataSQ.rear=x;SQ.rear=SQ.rear+1;B.SQ.rear=(SQ.rear+1)% maxsize;SQ.dataSQ.rear=x;C.SQ.rear=SQ.rear+1;SQ.dataSQ.rear=x;D.SQ.dataSQ.rear=x;SQ.rear=(SQ.rear+1)% maxsize;12.循环队列为空的条件是_（分数：2.00）A.CQ.r
5、ear=CQ.frontB.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeD.(CQ.rear+1)%maxsize=CQ.front13.A06，06每个元素占 5个单元，将其按列优先次序存储在起始地址为 1000的连续内存单元中，则元素 a5，5的地址为_（分数：2.00）A.1175B.1160C.1055D.114014.稀疏矩阵是指_（分数：2.00）A.元素少的矩阵B.有少量零元素的矩阵C.有少量非零元素的矩阵D.行数、列数很少的矩阵15.三角矩阵可压缩存储到数组哪个中_（分数：2.0
6、0）A.Mn(n+1)/2+1B.Mn(n+1)/2C.Mn/2D.M(n+1)/2二、填空题(总题数：13，分数：26.00)16.从宏观上看，数据组织应分成三个不同的层次，即数据、 1 和数据项。 （分数：2.00）17.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 1 和 2。 （分数：2.00）18.根据数据元素之间关系的不同特性，通常有 1、 2、 3、 4 四类基本逻辑结构，它们反映了四类基本的数据组织形式。 （分数：2.00）19.在表长为 n的顺序表上做删除运算，平均要移动的结点个数为 1。 （分数：2.00）20.队列又称为 1 的线性表。 （分数
7、：2.00）21.线性表常见的链式存储结构有单链表、 1 和 2，其中最简单的是单链表。 （分数：2.00）22.顺序表定位运算又称作 1，其基本操作是 2。 （分数：2.00）23.单链表中，增加头结点的目的是为了 1。 （分数：2.00）24.栈中的数据元素已经填满了，如果再进行栈操作，会发生 1。为了防止数据丢失，在进栈操作之前应该判断是否栈满。 （分数：2.00）25.在栈中，可进行插入和删除操作的一端称为 1，另一端称为 2。 （分数：2.00）26.在队列中，新插入的结点只能添加到 1，被删除的只能是排在 2 的结点。 （分数：2.00）27.如果值相同的元素或者零元素在矩阵中的分
8、布有一定规律，称此类矩阵为 1。 （分数：2.00）28.对称矩阵中有近半的元素可以通过其对称元素获得，若为每一对元素只分配一个存储空间，则可将 n 2 个元素压缩存储到 1 个元素的存储空间中。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.有一个整数序列，其输入顺序为 20，30，90，-10，45，78，试用栈将其输出序列变为 30，-10，45，90，78，20。请给出该整数序列进栈和出栈的操作步骤(可用 push(x)表示 x进栈，pop(x)表示x出栈)。 （分数：6.00）30.顺序存储结构与链式存储结构是什么关系? （分数：6.00）31.简述双向循环链表插
9、入运算的关键步骤(即在 p所指结点的后面插入一个新结点*t，写出需要修改的四个指针)。 （分数：6.00）32.试编写在带头结点的单链表上实现线性表基本运算定位和删除的算法。 （分数：6.00）33.设循环队列的容量为 40(序号从 039)，现经过一系列的入队和出队运算后，有(1)front=11，rear=19；(2)front=19，rear=11；问这两种情况下循环队列中的元素各有几个? （分数：6.00）四、算法设计题(总题数：2，分数：14.00)34.在一单链表中，存在多个结点，其数据值均为 50，试写一个算法统计该类结点的个数。 （分数：7.00）_35.假设一个算术表达式中可
10、包含两种括号：“(”，“)”；“”，“”，且这两种括号可按任意的次序嵌套使用。试用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法(可设表达式已存入字符型数组中)。 （分数：7.00）_数据结构导论自考题模拟 11答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.逻辑关系是指数据元素的_（分数：2.00）A.存储方式B.数据项C.结构D.关联方式 解析：考点 逻辑关系 解析 所谓逻辑关系是指数据元素之间的关联方式或者“邻接关系”。2.算法能正确地实现预定功能的特性称为_（分数：2.00）A.正确性 B.易读性C.健壮性D.时空性解
11、析：考点 算法的评价因素 解析 算法的正确性是指能正确地实现预定功能，满足具体问题的需要。3.for(i=0;in;i+) for(j=0;jn;j+) Aij=i*j; 上面算法的时间复杂度为_ A.O(1) B.O(n2) C.O(log2n) D.O(n)（分数：2.00）A.B. C.D.解析：考点 时间复杂度的计算 解析 第一个 for语句执行 n+1次，第二个 for语句执行 n*(n+1)次，第三行赋值语句执行 n*n次，可得整个程序段的时间函数为 T=(n+1)+n*(n+1)+n*n=2n 2 +2n+1，因此算法的时间复杂度为 O(n 2 )。4.带头结点的单链表 head
12、为空的判断条件为_（分数：2.00）A.head=NULLB.head!=NULLC.head-next=NULL D.head-next=head解析：考点 单链表 解析 带头结点的单链表 head为空的判断条件为 head-next=NULL。5.设顺序表有 10个元素，则在第 4个元素前插入一个元素所需移动元素的个数为_（分数：2.00）A.6B.7 C.8D.9解析：考点 顺序表的插入算法 解析 插入法的基本步骤是：将结点各向后移一位，以便空出第 i个位置；将 x置入该空位；表长加一，完成顺序表的插入。6.已知一个单链表中，指针 q指向指针 p的前驱结点，若在指针 q所指结点和指针 p
13、所指结点之间插入指针 s所指结点，则需执行_（分数：2.00）A.q-next=s;p-next=s;B.q-next=s;s-next=q;C.q-next=s;q-next=p;D.q-next=s;s-next=p; 解析：考点 单链表的插入算法 解析 单链表的插入步骤是：找到插入位置的前一个结点 q和后一个结点 p，生成一个结点 s，然后执行q-next=s;s-next=p 完成单链表的插入。7.循环链表中一个结点有多少个指针_（分数：2.00）A.1 B.2C.3D.0解析：考点 循环链表的特点 解析 循环链表即是将单链表的最后一个结点的指针域指向第一个结点。8.设指针 p指向循环
14、链表的某一结点，则双链表结构的对称性可用哪项来刻画_（分数：2.00）A.p-prior-next=p-next-nextB.p-prior-next=p-next-prior C.p-prior-prior=p-next-priorD.p-next-next=p-prior-prior解析：考点 双向链表的对称性 解析 双向链表的对称性可用等式 p=p-prior-next=p-next-prior。9.一个栈的入栈序列是 a、b、c、d、e，则栈的可能的输出序列是_（分数：2.00）A.cdabeB.decba C.cabdeD.dabec解析：考点 栈的存取原则 解析 栈的存取原则是后进
15、先出，A 选项中 cd先出栈，说明 ab已入栈且尚未出栈，a 不可能先于 b出栈，C、D 选项中 a不可能先于 b出栈，故选 B。10.设栈 S和队列 Q的初始状态为空，元素 e 1 ，e 2 ，e 3 ，e 4 ，e 5 和 e 6 依次通过栈 S，元素退栈后即进入队列 Q，若 6个元素的出队序列是 e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈 S的容量至少为_（分数：2.00）A.5B.2C.4D.3 解析：考点 栈和队列的特点 解析 栈后进先出，队列先进先出。11.顺序队列的入队列操作应为_（分数：2.00）A.SQ.dataSQ.rear=x;SQ.rear=SQ.
16、rear+1;B.SQ.rear=(SQ.rear+1)% maxsize;SQ.dataSQ.rear=x;C.SQ.rear=SQ.rear+1;SQ.dataSQ.rear=x; D.SQ.dataSQ.rear=x;SQ.rear=(SQ.rear+1)% maxsize;解析：考点 顺序队列的入队操作 解析 入队操作可用两条赋值语句：SQ.rear=SQ.rear+1;SQ.dataSQ.rear=x 完成。12.循环队列为空的条件是_（分数：2.00）A.CQ.rear=CQ.front B.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%m
17、axsize=(CQ.front+1)%maxsizeD.(CQ.rear+1)%maxsize=CQ.front解析：考点 循环队列为空的判断条件 解析 循环队列为空的判断条件 CQ.rear=CQ.front。13.A06，06每个元素占 5个单元，将其按列优先次序存储在起始地址为 1000的连续内存单元中，则元素 a5，5的地址为_（分数：2.00）A.1175 B.1160C.1055D.1140解析：考点 二维数组元素的地址计算 解析 a5，5的地址是 1000+(5+1)5+55=1175。14.稀疏矩阵是指_（分数：2.00）A.元素少的矩阵B.有少量零元素的矩阵C.有少量非零元
18、素的矩阵 D.行数、列数很少的矩阵解析：考点 稀疏矩阵的定义 解析 假设 m行 n列的矩阵有 t个非零元素，当 t远远小于 m*n时，则称矩阵为稀疏矩阵，根据定义选择 C。15.三角矩阵可压缩存储到数组哪个中_（分数：2.00）A.Mn(n+1)/2+1B.Mn(n+1)/2 C.Mn/2D.M(n+1)/2解析：考点 三角矩阵的存储 解析 为存储三角矩阵，采用数组 Mn(n+1)/2，把矩阵中上或下三角部分的 n(n+1)/2个元素存储在数组 M0Mn(n+1)/2-1的 n(n+1)/2个单元中，其中 n若非 0，则存放在数组 Mn(n+1)/2中。二、填空题(总题数：13，分数：26.0
19、0)16.从宏观上看，数据组织应分成三个不同的层次，即数据、 1 和数据项。 （分数：2.00）解析：数据元素 考点 数据组织的三个不同层次 解析 数据组织应分为三个不同的层次，即数据、数据元素、数据项。17.在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向 1 和 2。 （分数：2.00）解析：直接前驱 直接后继 考点 双链表的存储结构 解析 在双链表中，存储一个结点有三个域，一个是数据域，另两个是指针域，分别指向直接前驱和直接后继。18.根据数据元素之间关系的不同特性，通常有 1、 2、 3、 4 四类基本逻辑结构，它们反映了四类基本的数据组织形式。 （分数：2.0
20、0）解析：集合 线形 树形 图形 考点 逻辑结构的类别 解析 根据数据元素之间关系的不同特性，通常有集合、线形、树形、图形四类基本逻辑结构，它们反映了四类基本的数据组织形式。19.在表长为 n的顺序表上做删除运算，平均要移动的结点个数为 1。 （分数：2.00）解析：(n-1)/2 考点 队列的概念 解析 在表长为 n的顺序表上做删除运算，平均要移动的结点个数为(n-1)/2。20.队列又称为 1 的线性表。 （分数：2.00）解析：先进先出 考点 线性表的删除 解析 队列又称为先进先出的线性表。21.线性表常见的链式存储结构有单链表、 1 和 2，其中最简单的是单链表。 （分数：2.00）解
21、析：循环链表 双向循环链表 考点 线性表的链式存储结构 解析 线性表常见的链式存储结构有单链表、循环链表和双向循环链表，其中最简单的是单链表。22.顺序表定位运算又称作 1，其基本操作是 2。 （分数：2.00）解析：按值查找 比较 考点 线性表的定位 解析 顺序表定位运算又称作按值查找，其基本操作是比较。23.单链表中，增加头结点的目的是为了 1。 （分数：2.00）解析：方便算法的实现 考点 单链表中头结点的作用 解析 单链表中增加头结点的目的是为了方便算法的实现。24.栈中的数据元素已经填满了，如果再进行栈操作，会发生 1。为了防止数据丢失，在进栈操作之前应该判断是否栈满。 （分数：2.
22、00）解析：上溢 考点 进栈操作易出现的现象 解析 栈中的数据元素已经填满了，如果再进行栈操作，会发生上溢。为了防止数据丢失，在进栈操作之前应该判断是否桟满。25.在栈中，可进行插入和删除操作的一端称为 1，另一端称为 2。 （分数：2.00）解析：栈顶 栈底 考点 栈的基本概念 解析 在栈中，可进行插入和删除操作的一端称为栈顶，另一端称为栈底。26.在队列中，新插入的结点只能添加到 1，被删除的只能是排在 2 的结点。 （分数：2.00）解析：队列尾 队列首 考点 队列的插入和删除操作 解析 在队列中，新插入的结点只能添加到队列尾，被删除的只能是排在队列首的结点。27.如果值相同的元素或者零
23、元素在矩阵中的分布有一定规律，称此类矩阵为 1。 （分数：2.00）解析：特殊矩阵 考点 特殊矩阵的定义 解析 如果值相同的元素或者零元素在矩阵中的分布有一定规律，称此类矩阵为特殊矩阵。28.对称矩阵中有近半的元素可以通过其对称元素获得，若为每一对元素只分配一个存储空间，则可将 n 2 个元素压缩存储到 1 个元素的存储空间中。 （分数：2.00）解析：n(n+1)/2 考点 对称矩阵的压缩存储 解析 对称矩阵中有近半的元素可以通过其对称元素获得，若为每一对元素只分配一个存储空间，则可将 n 2 个元素压缩存储到 n(n+1)/2个元素的存储空间中。三、应用题(总题数：5，分数：30.00)2
24、9.有一个整数序列，其输入顺序为 20，30，90，-10，45，78，试用栈将其输出序列变为 30，-10，45，90，78，20。请给出该整数序列进栈和出栈的操作步骤(可用 push(x)表示 x进栈，pop(x)表示x出栈)。 （分数：6.00）解析：push(20)，push(30)，pop(30)，push(90)，push(-10)，pop(-10)，push(45)，pop(45)，pop(90)，push(78)，pop(78)，pop(20)。考点 栈的存取原则是后进先出30.顺序存储结构与链式存储结构是什么关系? （分数：6.00）解析：顺序存储结构是指存储结点存放在一个连
25、续的存储区里，利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。 链式存储结构是指每个存储结点除了含有一个数据元素之外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。 考点 数据元素之间的主要关联结构，即顺序存储结构和链式存储结构之间的关系31.简述双向循环链表插入运算的关键步骤(即在 p所指结点的后面插入一个新结点*t，写出需要修改的四个指针)。 （分数：6.00）解析：(1)t-prior=p; (2)t-next=p-next; (3)p-next-prior=t; (4)p-next=t; 考点 双向循环链表插入运算的关键步骤(指针的修
26、改)32.试编写在带头结点的单链表上实现线性表基本运算定位和删除的算法。 （分数：6.00）解析：(1)定位 在带头结点的单链表上实现的算法为： int LocateLiklis(LinkListhead, Data Type x) /求表 head中第一个值等于 x的结点的序号，若不存在这种结点，返回结果为 0 Node * p=head; /p是工作指针 p=p-next; /初始时 p指向首结点 int i=0; /i代表结点的序号，这里置初值为 0 while(p!=NULL p=p-next; if(p!=NULL) return i+1; else return 0; (2)删除
27、在带头结点的单链表上实现的算法为： void DeleteLinklist(LinkList head,int i) /删除表 head的第 i个结点 Node * q; if(i=o)q=head; else q=GetLinklist(head,i-1) /先找待删结点的直接前驱 if(q!=NULL /p 指向待删结点 q-next=p-next; /移出待删结点 free(p); /释放已移出结点 p的空间 else exit(“找不到要删除的结点“); /结点不存在 考点 带头结点单链表定位和删除运算的关键步骤(指针的修改)33.设循环队列的容量为 40(序号从 039)，现经过一系
28、列的入队和出队运算后，有(1)front=11，rear=19；(2)front=19，rear=11；问这两种情况下循环队列中的元素各有几个? （分数：6.00）解析：(1)(rear-front+max)% max=(19-11+40)%40=8 (2)(rear-front+max)% max=(11-19+40)%40=32 考点 循环队列的存取规则四、算法设计题(总题数：2，分数：14.00)34.在一单链表中，存在多个结点，其数据值均为 50，试写一个算法统计该类结点的个数。 （分数：7.00）_正确答案：()解析：int count(head) Node * head; int
29、n=0; /初始化值为 50的结点个数 p=head; while(p!=NULL) if(p-data=50)n+; p=p-next; return(n); 35.假设一个算术表达式中可包含两种括号：“(”，“)”；“”，“”，且这两种括号可按任意的次序嵌套使用。试用栈的运算编写判断给定表达式中所含括号是否正确配对出现的算法(可设表达式已存入字符型数组中)。 （分数：7.00）_正确答案：()解析：设表达式已存入字符数组 An中： void prool(An) IntStack(s); i=0;flag=true; while(in) else if(Ai=“)“)|(Ai=“) if(EmptyStack(s) flag=false; else x=GetTop(s); Switch(Ai) case“)“:if(x=“(“) Pop(s); else flag=false; break; case“:if(x=“) Pop(s); else flag=false; i+; 考点 栈的存取原则的应用
