河北大学数据库结构试卷
- 格式:doc
- 大小:52.50 KB
- 文档页数:5
数据库技术试题一、选择题1. 单个用户使用的数据视图的描述称为A. 外模式B. 概念模式C. 内模式D. 存储模式2. 子模式DDL用来描述A. 数据库的总体逻辑结构B. 数据库的局部逻辑结构C. 数据库的物理存储结构D. 数据库的概念结构3. 在DBS中,DBMS和OS之间的关系是A. 相互调用B. DBMS调用OSC. OS调用DBMSD. 并发运行4. 当关系R和S自然联接时,能够把R和S原该舍弃的元组放到结果关系中的操作是A. 左外联接B. 右外联接C. 外部并D. 外联接5. 下列聚合函数中不忽略空值 (null) 的是A. SUM(列名)B. MAX(列名)C. COUNT( * )D. AVG(列名)6. 设关系模式R (A,B,C),F是R上成立的FD集,F = {B→C},则分解ρ = {AB,BC}相对于FA. 是无损联接,也是保持FD的分解B. 是无损联接,但不保持FD的分解C. 不是无损联接,但保持FD的分解D. 既不是无损联接,也不保持FD 的分解7. 在数据库设计中,将ER图转换成关系数据模型的过程属于A. 需求分析阶段B. 逻辑设计阶段C. 概念设计阶段D. 物理设计阶段8. SQL中,下列涉及空值的操作,不正确的是A. AGE IS NULLB. AGE IS NOT NULLC. AGE = NULLD. NOT (AGE IS NULL)9. 一个关系中的候选关键字。
A .至多一个B .可多个C .必须多个D .至少 3 个10. DBMS中实现事务持久性的子系统是A. 安全性管理子系统B. 完整性管理子系统C. 并发控制子系统D. 恢复管理子系统11. SQL的全局约束是指基于元组的检查子句和A. 非空值约束B. 域约束子句C. 断言D. 外键子句12. 分布式数据库系统中分片模式和分配模式均是A. 全局的B. 局部的C. 分布的D. 集中的13. 属性类型允许是基本数据类型、结构类型和集合类型的模型是A. 平面关系模型B. 嵌套关系模型C. 复合对象模型D. 分布式关系模型14. 用树型结构表示实体之间联系的数据模型称为A.关系模型B.运算模型C.网状模型D.层次模型15. 数据库系统的核心是A.数据库B.数据库管理系统C.数据模型D.软件工具16. 在SQL语言中,与X BETWEEN 10 AND 20等价的表达式是A.X>10 AND X<20B.X>=10 AND X<20C.X>10 AND X<=20D.X>=10 AND X<=2017. 某个E-R图中有5个实体型,2个1∶n联系和2个m∶n联系,则该E-R图转换的关系模式个数至少是A.5个B.7个C.8个D.9个18. 若关系模式R(V,F)中的每一个决定属性集都包含候选码,则R属于A.2NFB.3NFC.BCNFD.4NF19. 若事务T对数据R已加X锁,则其他事务对数据RA.可以加S锁不能加X锁B.不能加S锁可以加X锁C.可以加S锁也可以加X锁D.不能加任何锁20.在目前的并行数据库体系结构中,可扩充性最高的是A.SMB.SDC.SND.SK21.数据的正确性和相容性是指数据库的A.完整性B.安全性C.并发性D.一致性22.下列不属于事务的特性的是A.隔离性B.一致性C.完整性D.原子性23.系统在运行过程中,由于某种硬件故障,使存储在外存上的数据部分损失或全部损失,这种情况属于A.事务故障B.系统故障C.介质故障D.运行故障24.E-R图是数据库设计的常用工具之一,它适用于建立数据库的A.概念模型B.逻辑模型C.结构模型D.物理模型25.数据库逻辑结构设计的主要任务是A.建立E-R图B.把数据送入数据库C.建立数据流图和需求说明书D.将E-R图转换为某个DBMS所支持的数据模型26.下面不是SQL语言优点的是。
河北大学课程考核试卷2007 —2008 学年第二学期05级计科、网工专业(类)考核科目计算机系统结构课程类别选修课考核类型考试考核方式闭卷卷别 B一、填空(共20分,每小题1分)1.流水线处理机中常见的三种相关是○1、○2、○3。
2.提高向量处理机性能的主要技术有○4、○5。
3.多处理机中保持Cache一致性的协议有○6、○7。
4.开发循环级并行的基本技术有○8、○9、○10。
5.○11、○12、○13。
6.“Cache-主存”层次中常用的映像规则有3种:全相联映像、○14、○15。
7.通道的种类有○16、○17和○18。
8.互连网络的表示方法有:图形表示法、○19和○20表示法。
二、名词解释(共15分,每小题3分)1.兼容机2.Amdahl定律3.存储系统4.总线5.系统的可用性三、简答(共20分,每小题5分)1.说明计算机系统结构、计算机组织与计算机实现之间的相互关系与影响。
2.CISC指令集结构存在的缺点。
3.分支预测缓冲的工作原理。
(以两个位的预测机制为例)4.简述通道的工作过程。
四、计算(共45分)1.假设我们考虑条件分支指令的两种不同设计方法如下:(a)CPUA:通过比较指令设置条件码,然后测试条件码进行分支;(b)CPUB:在分支指令中包括比较过程。
在两种CPU中,条件分支指令都占用2个时钟周期而所有其它指令占用1个时钟周期,对于CPUA,执行的指令中分支指令占30%;由于每个分支指令之前都需要有比较指令,因此比较指令也占30%。
由于CPUA在分支时不需要比较,因此假设它的时钟周期时间是CPUB的1.4倍。
哪一个CPU更快?(7分)如果CPUA 的时钟周期时间仅仅是CPUB的1.15倍,哪一个CPU更快呢?(6分)2.为提高流水线效率可采用哪两种主要途径来克服速度瓶颈?现有3段流水线,各段经过时间依次为△t、3△t、△t,(a)分别计算在连续输入3条指令时和30条指令时的吞吐率和效率。
【2021年】河北省石家庄市全国计算机等级考试数据库技术真题(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 在数据组织方法的层次方法是基于______ 的数据操作集合、完整性规则集合。
A.二维表B.链路结构C.图结构D.树结构2. 下列叙述不正确的是A.信息是现实世界事物的存在方式或运动状态的反应B.数据是描述现实世界事物的符号记录C.数据是信息的符号表示;信息是数据的内涵D.信息是数据的载体;数据是信息的语义解释3. 用户或应用程序看到的那部分的局部逻辑结构的描述是A.模式B.物理模式C.子模式D.内模式4.下列四条叙述中,正确的一条是A.操作系统是一种重要的应用软件B.外存中的信息可直接被CPU处理C.用机器语言编写的程序可以由计算机直接执行D.电源关闭后,ROM中的信息立即丢失5. 在TCP/IP参考模型中,不属于应用层协议的是A.IP协议B.FTP协议C.SMTP协议D.HTTP6. 下面说法不正确的是A.关键字是关系中能够用来唯一标识元组的属性B.在一个关系中,关键字的值不能为空C.一个关系中的所有候选关键字均可以被指定为主关键字D.关键字只能由单个的属性组成7. 数据库系统的三级层次模型中描述数据库中全体数据的逻辑结构和特征是( )。
A.内模式B.模式C.外模式D.存储模式8.计算机系统中判别是否有中断事件发生应是在( )A.进程切换时B.执行完一条指令后C.执行P操作后D.由用户态转入核心态时9. 有m个叶子节点的哈夫曼树,其节点总数是( )。
A.2mB.2m+1C.2m-1D.2(m+1)10. 在有关计算机软件的描述中,下面不正确的是A.软件就是计算机系统中的程序B.软件包括系统软件和应用软件C.软件是用户和机器的接芦D.软件使用户在不必了解计算机本身内部结构的情况下使用计算机二、填空题(10题)11.若一棵二叉树中只有叶结点和左、右子树皆非空的结点,设叶结点的个数为R,则左、右子树皆非空的结点个数是【】12. m阶B+树的根结点至多有______个子女。
2023年河北省唐山市全国计算机等级考试数据库技术测试卷(含答案) 学校:________ 班级:________ 姓名:________ 考号:________一、1.选择题(10题)1. 数据库FoxBASE和Oracle都是关系型数据库管理系统,但它们之间存在重要差别。
其差别之一是________。
A.FoxBASE可以使用汉字,而Oracle不可以使用汉字B.FoxBASE是单用户数据库,而Oracle是多用户数据库C.FoxBASE一个数据库是一个表,而Oracle一个数据库可以包含多个表D.FoxBASE在微机上运行,而Oracle在大中型机上运行2. 如果两个实体之间的联系是M:N,则实现1:M联系的方法是A.将两个实体转换成一个关系B.将两个实体转换的关系中,分别加入另一个关系的主码C.将“1”端实体转换的关系的主码,放人“M”端实体转换的关系中D.将“M”端实体转换的关系的主码,放人“1”端实体转换的关系中3. 数据库设计的概念设计阶段,表示概念结构的常用方法和描述工具是( )。
A.层次分析法和层次结构图B.数据流程分析法和数据流程图C.结构分析法和模块结构图D.实体联系法和实体联系图4. 数据库设计的需求阶段主要设计A.程序流程图B.程序结构图C.框图D.数据流程图5. 计算机网络的最大优点是A.共享资源B.增大容量C.加快计算D.节省人力6. 下面有关对象-关系数据库管理系统的叙述中,不正确的是A.数据类型不能嵌套B.可以创建新的数据类型C.继承性只适用于组合类型,子类继承超类的所有数据元素D.可以构造复杂对象的数据类型,集合是一种类型构造器7. 在对象—关系数据库系统中,创建新的基本数据类型需要说明的信息包括______。
Ⅰ.类型名Ⅰ.类型的存储信息Ⅰ.类型的地址Ⅰ.类型与ASCII码之间的转换A.Ⅰ、Ⅰ和ⅠB.Ⅰ、Ⅰ和ⅠC.Ⅰ、Ⅰ和ⅠD.全部8. 信息传输的安全应保证信息在网络传输的过程中不被泄漏和不被攻击,下列哪些属于在网络中攻击的方法?Ⅰ.复制信息Ⅰ.剪裁信息Ⅰ.窃听信息A.Ⅰ和ⅠB.Ⅰ和ⅠC.Ⅰ和ⅠD.全部9. 下列哪一项是由一组数据组成,这些数据物理上分布在计算机网络的不同结点上,逻辑上是属于同一个系统?A.分布式数据库系统B.并行数据库系统C.网络数据库系统D.层次数据库系统10. 设计数据库概念模型最著名、最实用的方法是P.P.S.Chen于1976年提出的什么方法?A.新奥尔良方法B.实体-联系方法C.逻辑结构设计方法D.物理设计方法二、填空题(10题)11.存储数据最小单位为(),一页大小为().12. 第三代数据库系统(或新一代数据库系统)是______技术和数据库技术相结合的系统。
河北东方学院2021 —2022 学年第一学期期末《数据结构》补考试卷一、选择题(共 15小题,每小题 2 分,共30分)1.某算法的时间复杂度为O(n^2),表明该算法的()。
[单选题] *A.问题规模是n^2B.执行时间等于n^2C.执行时间与n^2成正比(正确答案)D.问题规模与n^2成正比2.在一个单链表中,删除p结点(非尾结点)之后的一个结点的操作是()。
[单选题] *A.p->next=pB.p->next->next=p->nextC.p->next->next=pD.p->next=p->next->next(正确答案)3.设计算法要求算法能够提供异常处理,对不合理的数据进行检查,这属于算法设计的()目标。
[单选题] *A.正确性B.可读性C.可使用性D.健壮性(正确答案)4.在下列排序方法中,关键字比较的次数与记录的初始排列次序无关的是()。
[单选题] *A.希尔排序B.冒泡排序C.直接插入排序D.简单选择排序(正确答案)5.在一棵3叉树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为()个。
[单选题] *A.4B.5C.6(正确答案)D.76.若无向图G(V,E)中含有17个顶点,则保证图G在任何情况下,都是连通的需要的边数最少是()。
[单选题] *A.6B.15C.16(正确答案)D.217.在以下排序方法中,()是稳定的排序方法。
[单选题] *A.简单选择排序B.折半插入排序(正确答案)C.希尔排序D.快速排序8.一棵完全二叉树有1001个结点,其叶子结点的个数是()。
[单选题] *B.501(正确答案)C.254D.5059.经过以下栈运算后StackEmpty(s)的值为()。
InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,y) [单选题] *A.aB.bC.1(正确答案)D.010.已知一棵3阶B-树中有2047个关键字,则树的最大高度是()。
河北大学20 -20 学年第 学期《计算机信息网络》期末考试试卷(A 卷)(时间120分钟)开课院/系部: 姓名 学号 .一、单项选择题(每小题2分,共20分)1.计算机网络普遍采用的数据交换方式为: ( C )A.电路交换B.报文交换C.分组交换D.混合交换2. 从网络的分层模型的角度来看,通信子网的最高层是: ( B )A.数据链路层B.网络层C.运输层D.应用层3.以太网使用的协议是: ( B )A.CSMAB.CSMA/CDC.TCP/IPD.IEEE 802.54. 星型以太网常用的传输媒体是: ( A )A.双绞线B.同轴电缆C.光纤D.微波5. 地址解析协议ARP 的作用是:( A )A. 已知IP 地址查找MAC 地址B. 已知MAC 地址查找IPC. 已知域名查找IP 地址D. 已知IP 地址查找域名6. 在运输层提供的标识应用进程的机制是: ( C )A.IP 地址B.MAC 地址C.端口D.物理地址7. 下列IP 地址中错误的是: ( D )A. 11.11.11.11B. 111.111.111.111C. 211.211.211.211D. 311.311.311.3118.电子邮件服务器与电子邮件服务器之间使用的协议是: (B )A.UDPB.SMTPC.ARPD.IMAP9. 浏览器与WEB 服务器之间使用的传输协议是: ( B )A.HTMLB.HTTPC.FTPD.超连接10.下面属于公开密钥密码体系的是: ( C )A.替代密码B.置换密码C.RSAD.DES二、简答题(共45分) 1.什么是信道复用技术?常用的信道复用技术有哪几种?(8分)2.在连续ARQ 协议中,若发送序号用5个比特来编码,最大发送窗口为何不能取32?(7分)3.简述虚电路和数据报的区别。
(8分)4.IP 协议和UDP 协议提供的都是不可靠的无连接的服务,简述二者的区别和联系。
(7分)5.简述CSMA/CD 的工作原理。
2022年河北工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)一、选择题1、下列说法不正确的是()。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种:深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储, a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为()。
A.13B.33C.18D.403、以下与数据的存储结构无关的术语是()。
A.循环队列B.链表C.哈希表D.栈4、循环队列A[0..m-1]存放其元素值,用front和rear分别表示队头和队尾,则当前队列中的元素数是()。
A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front5、最大容量为n的循环队列,队尾指针是rear,队头:front,则队空的条件是()。
A.(rear+1)MOD n=frontB.rear=frontC.rear+1=frontD.(rear-1)MOD n=front6、下列选项中,不能构成折半查找中关键字比较序列的是()。
A.500,200,450,180 B.500,450,200,180C.180,500,200,450 D.180,200,500,4507、已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”,采用KMP算法进行匹配,第一次出现“失配”(s!=t)时,i=j=5,则下次开始匹配时,i和j的值分别()。
A.i=1,j=0 B.i=5,j=0 C.i=5,j=2 D.i=6,j=28、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为()。
A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、设X是树T中的一个非根结点,B是T所对应的二叉树。
A-6-1 河北大学课程考核试卷—学年第学期级专业(类)考核科目数据结构课程类别必修课考核类型考试考核方式闭卷卷别(注:考生务必将答案写在答题纸上,写在本试卷上的无效)一、单项选择题(共20分,每题2分)1、线性表采用链式存储时,结点的存储地址()A A、必须是不连续的、必须是不连续的、必须是不连续的B B B、连续与否均可、连续与否均可C 、必须是连续的、必须是连续的D D D、和头结点的存储地址相连续、和头结点的存储地址相连续2、下列说法不正确的是()A 、栈是一种运算受限的线性表、栈是一种运算受限的线性表 B B B、栈是一种后进先出的线性结构、栈是一种后进先出的线性结构C 、栈可以是线性结构也可以是非线性结构、栈可以是线性结构也可以是非线性结构D D D、栈可以用数组实现或链表来实现、栈可以用数组实现或链表来实现3、设循环队列中数组的下标范围是0 0 ~~ n-1 n-1,,f 表示队首元素的前驱位置,表示队首元素的前驱位置,r r 表示队尾元素的位置,则队列中元素个数为()。
A 、r-fB r-f B、、r-f+1C r-f+1 C、、(r-f+1)mod nD (r-f+1)mod n D、、(r-f+n)mod n4、一棵度数为4的树,它的4度结点有1个,个,33度结点有2个,个,22度结点有3个,1度结点有4个,问它的叶子结点有多少个?()A 、5B 5 B、、 6C 6 C、、 9D 9 D、、 115、在含n 个顶点和e 条边的有向图的邻接矩阵中,零元素的个数为()A 、e B 、2e C 、n 2-e D 、n 2-2e 6、已知一个有向图如右所示,则从定点a 出发进行深度优先遍历,不可能得到的DFS 序列为() A A、、 adbefcB B、、 adcefbC C、、 adcbfeD D、、 adefcb7、一棵深度为k 的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树的共有(共有( )个结点。
河 北 大 学 课 程 考 核 试 卷( 2005 —2006 学年第 1 学期)考核科目 数据结构 课程类别 选修 考核方式 闭卷 卷别_A _一、选择题(每题2分,共20分)( )1、如果线性表中最常用的操作是存取第 i 个元素及其前驱结点的值,则采用 存储方式节省时间。
A )单链表B )双链表C )单循环链表D )顺序表( )2、在一个链队列中,若f,r 分别为队首、队尾指针,则插入s 所指结点的操作为 A )f->next=s;f=s; B ) r ->next=s;r=s;C )s->next=r;r=s;D ) s->next=f;f=s;( )3、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反,则该二叉树定满足 A )所有的结点均无左孩子 B )所有的结点均无右孩子C )只有一个叶子结点D )是任意一棵二叉树( )4、设F是一个森林,B 是由F 变换得到的二叉树。
若F 中有n 个非终端结点,则B 中右指针域为空的结点有 个。
A )n-1B )nC )n +1D )n +2( )5、有10个结点的无向图至少有 条边才能确保其是连通图A )8B )9C )10D )11A —1()6、二叉排序树中,键值最小的结点一定A)左指针为空B)右指针为空C)左右指针均为空D)左右指针均非空()7、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的倍。
A)1/2B)1 C)2 D)4()8、设高度为h的二叉树上只有度为0和2的结点,则此二叉树中所包含的结点数至少为A)2*h B)2*h-1 C)2*h+1 D)h+1()9、一棵深度为k的平衡二叉树,其每个非终端结点的平衡因子均为0,则该树共有个结点。
A)2k-1-1B)2k-1+1 C)2k-1 D)2k+1()10、一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为A)79,46,56,38,40,80 B)84,79,56,38,40,46C)84,79,56,46,40,38D)84,56,79,40,46,38二、判断题(每题1分,共10分)()1、顺序存储方式只能用于线性结构,不能用于非线性结构。
河北大学20 —20 学年第 学期《计算机信息网络》考试试卷(时间120分钟)院/系 专业 姓名 学号一、是非题(请在括号内,正确的划√,错误的划×)(每题2分,共20分)1.所有以太网交换机端口既支持10BASE-T 标准,又支持100BASE-T 标准。
( F )2.Ethernet 、Token Ring 与FDDI 是构成虚拟局域网的基础。
( T )3.ATM 既可以用于广域网,又可以用于局域网,这是因为它的工作原理与Ethernet 基本上是相同的。
( F )4.Windows 操作系统各种版本均适合作网络服务器的基本平台。
( F ) 5.局域网的安全措施首选防火墙技术。
( T ) 6.帧中继的设计主要是以广域网互连为目标。
( T ) 7.应用网关是在应用层实现网络互连的设备。
( T )8.双绞线是目前带宽最宽、信号传输衰减最小、抗干扰能力最强的一类传输介质。
( F ) 9.PPP (Point-to-Point Protocol ,点到点协议)是一种在同步或异步线路上对数据包进行封装的数据链路层协议,早期的家庭拨号上网主要采用SLIP 协议,而现在更多的是用PPP 协议。
( T )10.如果多台计算机之间存在着明确的主/从关系,其中一台中心控制计算机可以控制其它连接计算机的开启与关闭,那么这样的多台计算机就构成了一个计算机网络。
( F )二、单项选择题(每小题2分,共40分) (请将正确答案填入下表中)A、PANB、LANC、MAND、WAN2.计算机网络中可以共享的资源包括()A、硬件、软件、数据、通信信道B、主机、外设、软件、通信信道C、硬件、程序、数据、通信信道D、主机、程序、数据、通信信道3.网络协议主要要素为()A、数据格式、编码、信号电平B、数据格式、控制信息、速度匹配C、语法、语义、同步D、编码、控制信息、同步4.采用专用线路通信时,可以省去的通信阶段是()A、建立通信线路B、建立数据传输链路C、传送通信控制信号和数据D、双方确认通信结束5.通信系统必须具备的三个基本要素是()A、终端、电缆、计算机B、信号发生器、通信线路、信号接收设备C、信源、通信媒体、信宿D、终端、通信设施、接收设备6.宽带传输通常使用的速率为()A、0 - 10Mbit/sB、1 - 2.5Mbit/sC、5 - 10Mbit/sD、0 - 400Mbit/s7.计算机网络通信系统是()A、电信号传输系统B、文字通信系统C、信号通信系统D、数据通信系统8.网络接口卡的基本功能包括:数据转换、通信服务和()A、数据传输B、数据缓存C、数据服务D、数据共享9.完成通信线路的设置与拆除的通信设备是()A、线路控制器B、调制解调器C、通信控制器D、多路复用器10.在星型局域网结构中,连接文件服务器与工作站的设备是()A、调制解调器B、交换器C、路由器D、集线器11.在OSI七层结构模型中,处于数据链路层与运输层之间的是()A、物理层B、网络层C、会话层D、表示层12.完成路径选择功能是在OSI模型的()A、物理层B、数据链路层C、网络层D、运输层13.下列功能中,属于表示层提供的是()A、交互管理B、透明传输C、死锁处理D、文本压缩14.在TCP/IP协议簇的层次中,解决计算机之间通信问题是在()A、网络接口层B、网际层C、传输层D、应用层15.对局域网来说,网络控制的核心是()A、工作站B、网卡C、网络服务器D、网络互连设备16.在中继系统中,中继器处于()A、物理层B、数据链路层C、网络层D、高层17.各种网络在物理层互连时要求()A、数据传输率和链路协议都相同B、数据传输率相同,链路协议可不同C、数据传输率可不同,链路协议相同D、数据传输率和链路协议都可不同18.网络管理系统中,管理对象是指()A、网络系统中各种具体设备B、网络系统中各种具体软件C、网络系统中各类管理人员D、网络系统中具体可以操作的数据19.Intranet技术主要由一系列的组件和技术构成,Intranet的网络协议核心是()A、ISP/SPXB、PPPC、TCP/IPD、SLIP20.网络管理信息系统的分析设计以()A、功能模块设计为中心B、数据分析为中心C、系统拓扑结构设计为中心D、系统规模分析为中心三、简答题(每小题5分,共20分)1、将网络协议进行分层有哪些好处?2、作为中间系统,转发器、网桥、路由器和网关有何区别3、UDP协议有何优点?4、计算机网络安全的内容包含哪几方面?四、应用题(每小题10分,共20分)1、IP 地址为192.72.20.111,属A 、B 、C 哪类地址?子网掩码选为255.255.255.224,是否有效?有效的IP 地址范围是什么?2. 设某路由器建立了如下的路由表,现在收到5个待转发的分组,其目的站IP 地址分别是: (1)130.138.139.130 (2)130.138.139.161 (3)130.138.139.200 (4)130.138.139.8(5)130.138.139.100分别计算其下一跳。
河北大学课程考核试卷
(2005 —2006学年第二学期)
考核科目数据结构课程类别必修课考核方式闭卷卷别B
注:所有题目的答案写清题号写在答题纸上。
一、单项选择题(共30分,每小题2分)
1.算法指的是()
A.计算机程序B.解决问题的计算过程
C.排序算法D.解决问题的有限运算序列
2.线性表采用链式存储时,结点的存储地址()
A.必须是不连续的B.连续与否均可
C.必须是连续的D.和头结点的存储地址相连续
3.一个栈的输入序列为1 2 3 4 5,则下列序列中不可能是栈的输出序列的是( )
A. 2 3 4 1 5
B. 5 4 1 3 2
C. 2 3 1 4 5
D. 1 5 4 3 2
4.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用( )存储方式最节省时间。
A.单链表
B.双向链表
C.带头结点的双循环链表
D.单循环链表
5.如下陈述中正确的是()
A.串是一种特殊的线性表 B.串的长度必须大于零
C.串中元素只能是字母 D.空串就是空白串
6.用某种排序方法对关键字序列(25,84,21,47,15,27,68,35,20)进行排序时,序列的变化情况如下:
20,15,21,25,47,27,68,35,84
15,20,21,25,35,27,47,68,84
15,20,21,25,27,35,47,68,84
则所采用的排序方法是()
A.选择排序B.希尔排序C.归并排序D.快速排序
7.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( ) A.e B.2e C.n2-e D.n2-2e
8.一棵左右子树均不空的二叉树在先序线索化后,其空指针域数为( )
A. 0
B. 1
C. 2
D.不确定
9.对有18个元素的有序表作二分查找,则查找A[3]的比较序列的下标依次为( )
A. 1,2,3
B. 9,5,2,3
C. 9,5,3
D. 9,4,2,3
10.数据表A中有10000个元素,如果仅要求求出其中最大的10个元素,则采用( )排序算法最节省时间。
A.堆排序
B.希尔排序
C.快速排序
D.直接选择排序
11.栈和队列的共同特点是( )
A.先进后出
B.先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
12.对线性表进行二分查找时,要求线性表必须( )
A.以顺序方式存储
B.以链接方式存储
C.以顺序方式存储,且结点按关键字有序排序
D.以链接方式存储,且结点按关键字有序排序
13.下列说法错误的是( )
A.一个图的邻接矩阵表示是唯一的
B.一个图的邻接表表示是不唯一的
C.一个图的生成树必为该图的极小连通子图
D.一个无环有向图的拓扑排序序列必唯一
14.下列排序算法中,某一趟结束后未必能选出一个元素放在其最终位置上的是( )
A.堆排序
B.冒泡排序
C.快速排序
D.直接插入排序
15.设有6个结点的无向图,该图至少应有( )条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
二、填空题(共20分,每空2分)
1.已知一棵完全二叉树中共有768结点,则该树中共有384 个叶子结点。
2.十字链表适合存放图,邻接多重表适合存放图。
3.已知数组A[1..10,1..10]为对称矩阵,其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中,则元素A[5,6]对应的地址是1225 。
4.在双链表中,在指针P所指结点前面插入一个结点S时的语句序列是:
S->next=P;S->prior=P->prior;P->prior=S; S->prior->next=S ;
5.二叉排序树上,结点的平衡因子定义为该结点(左)子树的高度减去该结点(右子树的高度)。
6.树的四种常用存储结构是:双亲表示法,孩子表示法,双亲孩子,孩子兄弟。
三.解答题(共20分,每小题5分)
1.用Kruskal 方法求出下图的一棵最小生成树。
2.已知一棵二叉树的先序遍历序列是ABCDEFGHIJK ,中序遍历序列是CDBGFEAHJIK ,请构造出该二叉树。
3.设无向图G 如图所示,试给出:
① 从V0出发的“深度优先”遍历序列(当存在多个邻接点时,标号小者优先)。
② 从V0出发的“广度优先”遍历序列(当存在多个邻接点时,标号小者优先)。
4.已知查找表为{19,01,23,14,55,20,84,27,68,11,10,77},设定哈希函数为:H(key)=key % 13 ,采用开放地址法的线性探测法解决冲突,试在0~16的哈希地址空间中对该关键字构造哈希表,并求出查找成功时的平均查找长度。
四.算法设计题(共30分,每小题10分)
要求:1)给出主要的数据类型定义。
2)用C语言描述算法,并对主要语句加注释。
1.已知一顺序表A,其元素值非递减有序排列,编写一个算法删除顺序表中多余的值相同的元素。
2.一个线性表中的元素为非零实数。
设计算法将正数或负数分开,使线性表前一半为负数,后一半为正数。
不必对元素排序,要求算法的时间复杂度为O(n)。
3.编写算法实现带头结点的单链表的逆置,请借助栈来实现。