当前位置：文档之家 › 浙江省2001年10月自学考试数据结构导论试题及答案

浙江省2001年10月自学考试数据结构导论试题及答案

  • 格式：doc
  • 大小：49.50 KB
  • 文档页数：5

浙江省2001年10月自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。

每小题1分，共14分)1.算法分析的目的是( )A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A.单链表B.双链表C.顺序表D.循环链表3.下面关于线性表的叙述中，错误的为( )A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域4.带头结点的单链表head为空的判断条件是( )A. head=NILB. head↑.next=NILC. head↑.next=headD. head< >NIL5.队列通常采用两种存储结构是( )A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构6.按照二叉树的定义，具有3个结点的二叉树有( )A.3B.4C.5D.67.二叉树的结构如下图所示，其中序遍历的序列为( )A.a,b,d,g,c,e,f,hB.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h8.深度为5的二叉树至多有( )个结点。

A.16B.32C.31D.109.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+边数10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。

A.nB.n+1C.n-1D.n/211.静态查找表与动态查找表二者的根本差别在于( )A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。

因为散列函数不是一对一的关系，所以选择好的( )方法是散列文件的关键。

A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理13.对于大文件的排序要研究在外设上的排序技术，即( )A.快速排序法B.内排序法14.设有5000个无序的元素，希望用最快的速度挑选出其中前50个最大的元素，最好选用( )法。

A.冒泡排序B.快速排序C.堆排序D.基数排序二、判断题(判断下列各题，正确的在题干后面括号内打“√”，错误的打“×”。

每小题2分，共20分)1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系。

( )2.在线性结构中，每个结点都有一个直接前驱和一个直接后继。

( )3.插入和删除是数组的两种基本操作。

( )4.在链栈的头部必须要设置头结点。

( )5.在二叉树中插入结点则该二叉树便不再是二叉树。

( )6.查找表的逻辑结构是集合。

( )7.静态查找表的检索与修改被分成两个不交叉的阶段分别进行。

( )8.在索引顺序文件中插入新的记录时，必须复制整个文件。

( )9.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。

( )10.对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是0(n2)( )三、填空题(每小题2分，共30分)1.程序设计的实质是________和________。

2.设由字符串a=′data′、b=′structure′、c=′-′,则a与c连接然后与b连接的结果为：________。

3.通常单链表的头结点指的是________；单链表的首结点指的是________。

4.一个队列的入队序列是a、b、c、d，则队列的输出序列为________。

5.栈结构通常采用的两种存储结构是________和________。

6.具有N个结点的完全二叉树的深度为________。

7.树的三种主要的遍历方法是：________、________和层次遍历。

8.在无向图的邻接矩阵A中，若A〔i,j〕等于1，则A〔j,i〕等于________。

9.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造________和解决________。

10.索引顺序表上的查找分两个阶段：(1)________；(2)________。

11.散列文件中的记录通常是成组存放的。

若干的记录组成一个存储单位，称作________。

12.就文件而言，按用户的观点所确定的基本存储单元称为________。

按外设的观点所确定的基本存储单元称为________。

13.文件的检索有三种方式：________存取、________存取和按关键字存取。

14.最简单的交换排序方法是________排序。

15.外排序的基本方法是________。

四、应用题(每小题6分，共18分)1.假定在学生的档案中含有：姓名、学号、年龄、性别。

如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。

2.有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。

3.有初始的无序序列为{98,65,38,40,12,51,100,77,26,88},给出对其进行归并排序(升序)的每一趟的结果。

五、设计题(每小题6分，共18分)1.假设用一个循环单链表来表示队列(称为循环链队)，该队列中只设一个队尾指针rear,不设队首指针。

请编写向循环链队中插入一个元素X的过程。

2.以邻接表为存储结构，写出连通图的深度优先搜索算法。

3.设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用散列函数：H(key)=key MOD 13, 采用线性探测法解决冲突，试在0～18的散列地址空间中对该关键字序列构造散列表。

浙江省2001年10月自学考试数据结构导论试题参考答案课程代码：02142一、单项选择题(每小题1分，共14分)1.C2.B3.D4.B5.A6.C7.B8.C9.A 10.C11.B 12.D 13.C 14.C二、判断题(每小题2分，共20分)1. ×2. ×3. ×4. ×5. ×6. √7. √8. ×9. ×10. √三、填空题(每小题2分，共30分)1.(1)数据表示(2)数据处理。

2.′data-structure′。

3.(1)在单链表第一个结点之前增设的一个类型相同的结点(2)表结点中的第一个结点。

4. a、b、c、d。

5.(1)顺序存储结构(2)链表存储结构。

6.〔log2N〕+1。

7.(1)先根遍历(2)后根遍历。

8.1。

9.(1)散列函数(2)冲突。

10.(1)确定待查元素所在的块(2)在块内查找待查的元素。

11.桶。

12.(1)逻辑结构(2)物理结构。

13.(1)顺序(2)直接。

14.冒泡排序。

15.归并。

四、应用题(每小题6分，共18分)1.顺序实现：const maxsize∶=100; ｛顺序表的容量｝type datatype=record ｛档案数据类型｝name∶string〔10〕;｛姓名｝number∶integer;｛学号｝sex∶boolean;｛性别｝age∶integer;｛年龄｝end;type slist =recorddata∶array 〔1..maxsize〕of datatype;last∶integer;end;链接实现：type pointer=↑node;node=recordname∶string 〔10〕;｛姓名｝number∶interger；｛学号｝sex∶boolean;｛性别｝age∶integer;｛年龄｝next∶pointer;｛结点的后继指针｝end;2.d a相应的哈夫曼编码为：a:001 b:10 c:01 d:000 e:11画出正确的哈夫曼树给4分，写出相应哈夫曼编码给2分3.初始无序序列：98 65 38 40 12 51 100 77 26 88 ｛98｝｛65｝｛38｝｛40｝｛12｝｛51｝｛100｝｛77｝｛26｝｛88｝第一次归并：｛65 98｝｛38 40｝｛12 51｝｛77 100｝｛26 88｝第二次归并：｛38 40 65 98｝｛12 51 77 100｝｛26 88｝第三次归并：｛12 38 40 51 65 77 98 100｝｛26 88｝第四次归并：｛12 26 38 40 51 65 77 88 98 100｝五、设计题(每小题6分，共18分)1.PROCEDURE insert (V AR rear∶pointer; x∶integer);V AR head, tmp∶pointer;BEGINnew(tmp);tmp↑.data∶=x;if (rear=NIL) then ｛循环队列为空，新结点是队列的首结点｝BEGINrear∶=tmp;rear↑.next∶=tmp;ENDelse ｛队列不空，将新结点插入在队列尾｝BEGINhead∶=rear↑.next;rear↑.next∶=tmp;rear∶=tmp;rear↑.next∶=head;ENDEND;2.procedure dfs(g:adj—list;v1∶integer);｛从v1出发，深度优先遍历图g｝beginwrite(v1);visited(v1)∶=true; ｛标志v1已访问｝p=g〔v1〕.link; ｛找v1的第一个邻接点｝while p< >nil do〔if not (visited〔p↑.vertex〕)then dfs(g,p↑.vertex);p∶=p↑.next〕｛找v1的下一个邻接点｝end;以邻接表为存储结构，连通图的深度优先搜索就是顺序查找链表。

3.构造过程如下：H(19)=19 MOD 13=6H(01)=01 MOD 13=1H(23)=23 MOD 13=10H(14)=14 MOD 13=1(冲突)H(14)=(1+1) MOD 19=2H(55)=55 MOD 13=3H(20)=20 MOD 13=7H(84)=84 MOD 13=6 (冲突)H(84)=(6+1) MOD 19=7 (仍冲突)H(84)=(6+2) MOD 19=8H(27)=27 MOD 13=1 (冲突)H(27)=(1+1) MOD 19=2 (冲突)H(27)=(1+2) MOD 19=3 (仍冲突)H(27)=(1+3) MOD 19=4H(68)=68 MOD 13=3 (冲突)H(68)=(3+1) MOD 19=4 (仍冲突)H(68)=(3+2) MOD 19=5H(11)=11 MOD 13=11H(10)=10 MOD 13=10 (冲突)H(10)=(10+1) MOD 19=11 (仍冲突)H(10)=(10+2) MOD 19=12H(77)=77 MOD 13=12 (冲突)H(77)=(12+1) MOD 19=13因此，各关键字相应的地址分配如下：address(01)=1address(14)=2address(55)=3address(27)=4address(68)=5address(19)=6address(20)=7address(84)=8address(23)=10address(11)=11address(10)=12address(77)=13其余的地址中为空。

合集下载

高等教育自学考试全国统一命题考试数据结构导论试卷及参考答案

高等教育自学考试全国统一命题考试数据结构导论试卷及参考答案

20XX年(下)高等教育自学考试全国统一命题考试数据结构导论试卷及参考答案第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。

请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1．数据的基本单位是 ( )A．数据项 B．数据类型C．数据元素 D．数据变量2．下列程序的时间复杂度为 ( )3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是 ( )A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表4．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动的元素的个数是( )A．n—i B．n—i+1C．n—i一1 D．i5．顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为 ( )6．循环队列sq中，用数组elem[0··25]存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，设当前sq．front为20，sq．rear为12，则当前队列中的元素个数为 ( )A．8 B．16C．17 D．18A．13 B．35C．17 D．368．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为 ( ) A．3 B.4C．5 D．69．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为( )A．24 B．25C．98 D．9910．可以惟一地转化成一棵一般树的二叉树的特点是 ( )A．根结点无左孩子 B．根结点无右孩子C．根结点有两个孩子 D．根结点没有孩子11．有n个结点的有向完全图的弧数是( )12．设图的邻接链表如题l2图所示，则该图的边的数目是 ( )A．4 B．5C．10 D．201 3．已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分检索值为90的元素时，检索成功需比较的次数是 ( )A．1 B．2C．3 D．414．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是 ( ) A．选择排序 B．快速排序C．冒泡排序 D．插入排序15．排序算法中，不稳定的排序是 ( )A．直接插入排序 B．冒泡排序C．堆排序 D．归并排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

全国自学考试数据结构导论试题与答案解析[4套]

全国自学考试数据结构导论试题与答案解析[4套]

全国2011年1月自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中，度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>，<V1,V3>，<V1,V4>，<V2,V5>，<V3,V5>,<V3,V6>，<V4,V6>，<V5,V7>,，<V6,V7>}，则图G的拓扑序列是( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义，表述正确的是( )A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( )A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；do{x=x+5*i；i--；}while （i>0）；的时间复杂度为( )A.O（1）B.O（n）C.O（n2）D.O(n3)8.与串的逻辑结构不同的．．．数据结构是( )A.线性表B.栈C.队列D.树9.二叉树的第i（i≥1）层上所拥有的结点个数最多为( )A.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( ) A.p->next=p->next->next B.p=p->nextC.p=p->next->nextD.p->next=p11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=″ABCDEFG″，S2=″PQRST″，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2)),SUBSTR(S1,LENGTH(S2),2))后S的结果为( )A.″BCQR″B.″BCDEF″C.″BCDEFG″D.″BCDEFEF″13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( )A.LL型B.LR型C.RL型D.RR型14.如果结点A有3个兄弟结点，而且B为A的双亲，则B的度为( )A.1B.3C.4D.515.数据表A中每个元素距其最终位置较近，则最省时间的排序算法是( )A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

2001年10月浙江省高等教育自学考试互联网数据库试题

2001年10月浙江省高等教育自学考试互联网数据库试题

⼀、填空题（每空1分，共20分） 1.实体之间的联系按照联系⽅式的不同可分为______、______、______. 2.数据库系统的核⼼是______. 3.在关系模型中，实体以及实体间的联系都是⽤______来表⽰的。

4.在关系代数中专门的关系运算包括______、投影、______、除等运算。

5.1975年由IBM公司的M.Zloof提出的QBE语⾔是⼀个很有特⾊的______语⾔。

6.SQL语⾔集数据查询、______、______和______功能于⼀体，充分体现了关系数据语⾔的特点和优点。

7.数据库管理系统保证数据安全的主要措施是进⾏______. 8.⼈们已经提出了许多种类型的数据依赖，其中最重要的是______和______. 9.关系模式由3NF转化为BCNF是消除了主属性对码的______和______. 10.数据库设计应包括两个⽅⾯的内容：______设计和______设计。

11.CGI规范允许Web服务器执⾏______，并将它们的输出发送给浏览器。

12.数据库技术与______技术相结合，形成了⾯向对象数据库系统。

⼆、单项选择题（在每⼩题的四个备选答案中，选出⼀个正确答案，并将正确答案的序号填在题⼲的括号内。

每⼩题2分，共20分） 1.数据库类型是按照（）来划分的。

A.⽂件形式B.数据模型C.记录形式D.数据存取⽅法 2.关系演算的基础是（）A.形式逻辑中的逻辑演算B.形式逻辑中的关系演算C.数理逻辑中的谓词演算D.数理逻辑中的形式演算 3.若要求分解保持函数依赖，那么模式分解⼀定能够达到（）A. 2NFB. 3NFC. BCNFD. 1NF 4.1级封锁协议加上T要读取的数据R加S锁，这是（）A. 3级封锁协议B. 4级封锁协议C. 2级封锁协议D. 1级封锁协议 5.建⽴数据字典的时机是（）A.需求分析阶段B.数据库物理设计阶段C.数据库实施D.概念结构设计阶段 6.和POST⽅法⽐较起来，GET⽅法具有的特点是（） A. GET⽅式⽐POST⽅式安全 B. GET⽅式不如POST⽅式快 C. GET⽅式不如POST⽅式安全 D. 以上都不对 7.鉴于Java的特点，它最适合的计算环境是（）A.并⾏计算环境B.分布式计算环境C.⾼强度计算环境D.开放式计算环境 8.⽤基于Windows9X的PWS添加多个Web站点的⽅法是（） A. Windows9X的PWS根本就不⽀持多个Web站点 B. 使⽤Microsoft MultiThread扩展件 C. 使⽤Microsoft MultiHost扩展件 D. 使⽤Microsoft MultiTCP/IP扩展件 9.⽀持从远程服务器上添加虚拟⽬录的Web服务器有（） A. Windows9X的PWS B. WindowsNT Server的IIS C.WindowsNT Server的Transaction Server D. Windows9X的IIS 10.Replication Server属于哪个数据库产品（）A. DB2B. OracleC. InformixD. Sybase 三、简答题（每⼩题6分，共30分） 1.简述数据库管理系统的功能。

数据库原理试题及答案2

数据库原理试题及答案2

全国2001年10月自学考试数据库原理试题及答案2作者：ryan 点击：时间：2003-10-11 上午 23:05:00 来源：第一部分选择题 (共30分)一、单项选择题 (本大题共15小题，每小题2分，共30分) 在每小题列出的四个选项中只有一个是符合题目要求的，请将其代码填在题后的括号内。

错选或未选均无分。

1. 单个用户使用的数据视图的描述称为【】A. 外模式B. 概念模式C. 内模式D. 存储模式2. 子模式DDL用来描述【】A. 数据库的总体逻辑结构B. 数据库的局部逻辑结构C. 数据库的物理存储结构D. 数据库的概念结构3. 在DBS中，DBMS和OS之间的关系是【】A. 相互调用B. DBMS调用OSC. OS调用DBMSD. 并发运行4. 五种基本关系代数运算是【】A. ∪，-，×，π和σB. ∪，-，∞，π和σC. ∪，∩，×，π和σD. ∪，∩，∞，π和σ5. 当关系R和S自然联接时，能够把R和S原该舍弃的元组放到结果关系中的操作是【】A. 左外联接B. 右外联接C. 外部并D. 外联接6. 下列聚合函数中不忽略空值 (null) 的是【】A. SUM (列名)B. MAX (列名)C. COUNT ( * )D. AVG (列名)7. 设关系模式R (A，B，C)，F是R上成立的FD集，F = {B→C}，则分解ρ= {AB，BC}相对于F 【】A. 是无损联接，也是保持FD的分解B. 是无损联接，但不保持FD的分解C. 不是无损联接，但保持FD的分解D. 既不是无损联接，也不保持FD 的分解8. 关系模式R分解成ρ= {R1，…，Rk}，F是R上的一个FD集，那么R中满足F的每一个关系r，与其投影联接表达式mρ(r) 间的关系满足【】A. rÍ mρ(r)B. mρ(r) Í rC. r = mρ(r)D. r≠mρ(r)9. 在数据库设计中，将ER图转换成关系数据模型的过程属于【】A. 需求分析阶段B. 逻辑设计阶段C. 概念设计阶段D. 物理设计阶段10. SQL中，下列涉及空值的操作，不正确的是【】A. AGE IS NULLB. AGE IS NOT NULLC. AGE = NULLD. NOT (AGE IS NULL)11. 如果事务T获得了数据项Q上的排它锁，则T对Q 【】A. 只能读不能写B. 只能写不能读C. 既可读又可写D. 不能读不能写12. DBMS中实现事务持久性的子系统是【】A. 安全性管理子系统B. 完整性管理子系统C. 并发控制子系统D. 恢复管理子系统13. SQL的全局约束是指基于元组的检查子句和【】A. 非空值约束B. 域约束子句C. 断言D. 外键子句14. 分布式数据库系统中分片模式和分配模式均是【】A. 全局的B. 局部的C. 分布的D. 集中的15. 属性类型允许是基本数据类型、结构类型和集合类型的模型是【】A. 平面关系模型B. 嵌套关系模型C. 复合对象模型D. 分布式关系模型第二部分非选择题 (共70分)二、填空题 (本大题共10小题，每小题1分，共10分，将正确的答案写在每小题的空格内。