您的当前位置：首页 2011山东专升本_计算机科学与技术_专业课模拟试题

2011山东专升本_计算机科学与技术_专业课模拟试题

来源：抵帆知识网

山东校园网：www.xyw.me 山东招生考试资讯网

计算机科学与技术模拟试题

《操作系统》模拟试题一

一、填空题（本题共25分，每题5分）

1、进程的逻辑地址到__________地址的转换，称为重定位。 2、分区管理分为__________和__________两种方式。

3、处理机在执行系统程序时的状态称为__________，在执行用户程序时的状态称为__________。 4、如果为了使所有进程都有机会运行，最好采用的调度算法是__________。 5、对记录式文件，操作系统为用户存取文件信息的最小单位是__________。二、（本题满分为10分）

以打印机为例说明SPOOLING的工作原理，系统如何利用SPOOLING技术将打印机模拟为虚拟打印机。

三、（本题满分为10分）对于如下的页面访问序列：

1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5

当内存块数量分别为3和4时，试问：使用FIFO、LRU置换算法产生的缺页中断是多少？（所有内存开始时都是空的，凡第一次用到的页面都产生一次缺页中断）

四、（本题满分为15分）

某虚拟存储器的用户编程空间共32个页面，每页为1KB，内存为16KB。假定某时刻一用户页表中已调入内存的页面的页号和物理块号的对照表如下：

页号 0 物理块号 3 更多专升本资料请到山东校园网：www.xyw.me 1

山东校园网：www.xyw.me 山东招生考试资讯网

1 2 3 7 11 8 则逻辑地址0A5C(H)所对应的物理地址是什么？要求：写出主要计算过程。

五、（本题满分为15分）

假定具有5个进程的进程集合P＝｛P0,P1,P2,P3,P4｝,系统中有三类资源A，B和C。其中A类资源有10个，B类资源有5个，C类资源有7个。假定在某时刻有如下状态： Allocation Max Available A B C A B C A B C P0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2 P3 2 1 1 2 2 2 P4 0 0 2 4 3 3 试给出Need，并说明当前系统是否处于安全状态，如果是，给出安全序列。如果不是，说明理由。答案

一、1、物理 2、静态分区动态分区 3、系统态用户态 4、轮转法 5、记录

二、当用户进程请求打印输出时，Spooling系统同意打印输出，但并不真正把打印机分配给该用户进程，而只为它做两件事：1，由输出进程在输出井中为之申请一空闲盘块区，并将要打印的数据送入其中；2，

更多专升本资料请到山东校园网：www.xyw.me 2

山东校园网：www.xyw.me 山东招生考试资讯网

输出进程再为用户进程申请一张空白的用户请求打印表，并将用户的打印要求填入表中，再将该表挂到请求打印队列之上。如果还有进程要求打印输出，系统仍可以接受该请求，同样做上面的工作。如果打印机空闲，输出进程将从请求打印队列的队首取出一张请求表，根据表中的要求将要打印的数据从输出井传送到内存缓冲区，再由打印机进行打印。打印完毕，输出进程再查看请求打印队列中是否还有等待要打印的请求表，若有，再取出一张表，并根据其中的要求进行打印，如此下去，直至请求队列为空位置，输出进程才将自己阻塞起来，等待下次再由打印请求时才被唤醒。三、FIFO淘汰算法：

内存块为3时，缺页中断（或称缺页次数、页面故障）为9；内存块为4时，缺页中断为10。 LRU淘汰算法：

内存块为3时，缺页中断为10；内存块为4时，缺页中断为8。四、125C（H）（要求写出计算步骤）

[分析]页式存储管理的逻辑地址分为两部分：页号和页内地址。

由已知条件“用户编程空间共32个页面”，可知页号部分占5位；由“每页为1KB”，1K=2，可知内页地址占10位。由“内存为16KB”，可知有16块，块号为4位。

逻辑地址0A5C（H）所对应的二进制表示形式是：000 1010 0101 1100 ，根据上面的分析，下划线部分为页内地址，编码 “000 10” 为页号，表示该逻辑地址对应的页号为2。查页表，得到物理块号是4（十进制），即物理块地址为：01 00 ，拼接块内地址10 0101 1100，得01 0010 0101 1100，即125C（H）。五、当前系统处于安全状态，安全序列如下求解： work = Available = (3 , 3 , 2 ) 寻找 Needj <= work = ( 3 , 3 , 2 ) ( j = 0 , 1 , 2 , 3 , 4) j = 1 Need1 = (1 ,2 ,3 ) < = (3 , 3 , 2 )

work : = (3 , 3 , 2 ) + (2 ,0 ,0 ) = (5 , 3 , 2 )

寻找 Needj <= work = ( 5 , 3 , 2 ) ( j = 0 , 2 , 3 , 4) j = 3 Need3 = (0 ,1 ,1 ) < = (5 , 3 , 2 ) work : = (5 , 3 , 2 ) + (2 ,1 ,1 ) = (7 , 4 , 3 ) 寻找 Needj <= work = (7 , 4 , 3 ) ( j = 0 , 2 , 4) 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

j = 4 Need4 = (4 ,3 ,1 ) < = (7 , 4 , 3 ) work : = (7 , 4 , 3 ) + (0 ,0 ,2 ) = (7 , 4 , 5) 寻找 Needj <= work = (7 , 4 , 5) (j = 0 , 2 ) j = 2 Need2 = (6 ,0 ,0 ) < = (7 , 4 , 5 )

work : = (7 , 4 , 5 ) + (3 ,0 ,2 ) = (10 , 4 , 7) 寻找 Needj <= work = (10 , 4 , 7) ( j = 0 )

j = 0 work : = (10 , 4 , 7 ) + (0 ,1 ,0 ) = (10 , 5 , 7) 所以安全序列为＜P1，P3，P4，P2，P0＞。

《操作系统》模拟试题二一、填空题（本题共25分，每题5分）

1、操作系统是计算机系统的一种系统软件，它以尽量合理、有效的方式组织和管理计算机的__________，并控制程序的运行，使整个计算机系统能高效地运行。

2、操作系统中，对信号量S的P原语操作定义中，使进程进入相应等待队列等待的条件是__________。 3、银行家算法中，当一个进程提出的资源请求将导致系统从__________进入__________时，系统就拒绝它的资源请求。

4、在请求页式存储管理中，若采用FIFO页面淘汰算法，则当分配的页面数增加时，__________的次数可能增加也可能减少。 5、采用段式存储管理的系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是__________。二、（本题满分为10分）

在操作系统中，P操作和V操作各自的动作是如何定义的？

三、（本题满分为10分）

假设一个活动头磁盘有200道, 编号从0-199. 当前磁头正在143道上服务, 并且刚刚完成了125道的请求. 现有如下访盘请求序列(磁道号):

86, 147, 91, 177, 94, 150, 102, 175, 130 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

试给出采用下列算法后磁头移动的顺序和移动总量(总磁道数). (1). 先来先服务(FCFS)磁盘调度算法. (2). 最短寻道时间优先(SSTF)磁盘调度算法.

(3). 扫描法(SCAN)磁盘调度算法.(假设沿磁头移动方向不再有访问请求时, 磁头沿相反方向移动.)

四、（本题满分为15分）

设系统中有三类资源A、B和C，又设系统中有5个进程P1，P2，P3，P4和P5.在T0时刻系统状态如下：

最大需求量已分配资源量剩余资源量 A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 P2 4 3 3 3 1 1 P3 10 1 3 4 1 3 P4 3 3 3 3 2 2 P5 5 4 6 1 1 3 (1) 系统是否处于安全状态？如是，则给出进程安全序列.

(2) 如果进程P5申请1个资源类A、1个资源类B和1个资源类C，能否实施分配？为什么？

五、（本题满分为15分）

有n+1个进程A1, A2, ...An 和 B:

(1) A1,...An通过同一个缓冲区各自不断地向B发送消息, B不断地取消息, 它必须取走发来的每一个消息. 刚开始时缓冲区为空. 试用P、V操作正确实现之. (2) 若缓冲区个数增至m个, 试用P、V操作实现正确的通讯.

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

答案：

一、1、资源 2、S<0 3、安全状态不安全状态 4、缺页中断 5、216

二、在操作系统中，P操作和V操作各自的动作是如何定义的？答：P操作顺序执行下述两个动作： ①信号量的值减1，即S=S-1； ②如果S≥0，则该进程继续执行；

如果S＜0，则把该进程的状态置为阻塞态，把相应的PCB连入该信号量队列的末尾，并放弃处理机，进行等待（直至其它进程在S上执行V操作，把它释放出来为止）。 V操作顺序执行下述两个动作： ①S值加1，即S=S+1；

②如果S＞0，则该进程继续运行；

如果S≤0，则释放信号量队列上的第一个PCB（即信号量指量指针项所指向的PCB）所对应的进程（把阻塞态改为就绪态），执行V操作的进程继续运行。三、（1）86，147，91，177，94，150，102，175，130 （2）当前磁头在143道上：

147，150，130，102，94，91，86，175，177 （3）当前磁头在143道上，并且刚刚完成125道的请求 147，150，175，177，130，102，94，91，86 四、（1）最大需求量已分配资源量剩余资源量尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 1 1 3 4 3 3 系统是处于安全状态，安全序列为：P4，P2，P1，P3，P5 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

（2）P5申请（1，1，1）

最大需求量已分配资源量剩余资源量尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 1 0 0 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 2 2 4 3 2 2 不能实施分配，因为分配后找不到安全序列，系统将处于不安全状态. 五、(1) n+1个进程P1, P2, ...,Pn 和 Q ，一个缓冲区 Pi ( i=1,..,n): Repeat 生产消息； P(S1);

向缓冲区送消息； V(S2) Until False Q: Repeat P(S2); 从缓冲区取消息； V(S1)；处理消息； Until False S1=1, S2=0 (2) k个缓冲区 Pi ( i=1,..,n): Repeat 生产消息；

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

P(S1); P(mutex);

向BUFFER[l]中送消息； l:=(l+1) mod k; V(mutex); V(S2) Until False S1=k;S2=0;mutex=1;l=0;ll=0 Q: Repeat P(S2); P(mutex);

从BUFFER[ll]取消息； ll:=(ll+1) mod k; V(mutex); V(S1) Until False

微机原理与接口技术（七）

一、填空题（每题5分，共5个题，总分25分）

1．8086/8088 CPU具有两种外部中断，它们是______和______。 2．（234）10＝______2＝______16

3第二代CPU使用的电子器件是______；第三代CPU采用的电子器件是______。 4．EIA RS-232C 的TXD和RXD数据线上的电平逻辑1=______V；逻辑0=______V。

5．在8086中，段寄存器CS＝1200H，指令指针寄存器IP＝FF00H，此时指令的物理地址为：______。二、（10分）什么是中断源？8086通常的中断源有哪些？

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

三、（10分）何为逻辑地址？何为物理地址？它们俩者之间有何关系？

四、（15分）编写程序段实现如下功能：（1）将立即数17H送DL；立即数7FH送AL。

（2）从DX所指的端口中读取一个字节至AL；将AX中的一个字输出至DX和DX＋1所指的端口中。

五、（15分）在1000H开始的内存中，放有1000个ASCII字符，请设计一程序，将这串ASCII字符以异步串行通信方式从8255A PB0输出，采用偶校验、一位起始位、一位终止位、波特率500 (可调用1ms软件定时程序 “D1MS”)。

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

8255A接口连接图如下： 8255A工作方式控制字如下∶ D7 特征位答案一、

1、可屏蔽中断，非屏蔽中断 2、 11101010，EA 3、半导体，集成电路 4、-3~-15，+3~+15 5、21F00H

二、引起中断的原因或能发出中断申请的来源称为中断源。通常中断源有以下几种：

（1）一般的输入输出设备。如键盘、行打印机等。（2）数据通道中断源。如磁盘、磁带等。（3）实时时钟。

（4）故障源。如电源掉电等。更多专升本资料请到山东校园网：www.xyw.me

D6 A组方式 D5 D4 A口 D3 C4～7 D2 B组方式 D1 B口 D0 C0～3 山东校园网：www.xyw.me 山东招生考试资讯网

三、物理地址是存储器的实际地址，一个存储单元的物理地址是惟一，逻辑地址为程序设计中所使用的存储器地址，它由段基址和地内偏移地址两部份构成，物理地址=段基址×16＋偏移地址，可见一个存储单元的逻辑地址可以有若干个四、（1）MOV DL,17H MOV AL,7FH （2）IN AL,DX OUT DX,AX

五、MOV SI ,1000H MOV CX ,1000

MOV DX ,30FH MOV AL ,10000000B OUT DX,AL MOV DX,30DH

MOV AL ,0FFH OUT DX ,AL CALL D1MS CALL D1MS

L1: MOV BL ,8 MOV AL ,0 OUT DX ,AL CALL D1MS CALL D1MS MOV AL ,[SI] AND AL ,AL JP L2 OR AL ,80H L2: OUT DX ,AL CALL D1MS

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

CALL D1MS ROR AL,1 DEC BL JNZ L2 MOV AL ,0FFH OUT DX ,AL CALL D1MS CALL D1MS INC SI LOOP L1 HLT；

微机原理与接口技术（九）

一、填空题（每题5分，共5个题，总分25分） 1、数制转换：247.86= H =______________BCD 2、8086CPU中典型总线周期由____个时钟周期组成，其中T1期间，CPU输出______信息。 3、异步串行通信数据格式由起始位、位、位和位等4部分组成。

4、如果一个程序在执行前（CS）=0A7F0H，（IP）=2B40H，该程序的起始物理地址是__ 。5、用4K×4bit的存储器芯片构成32KB的存储器, 所需要的芯片数是片。二、（10分）EU与BIU各自的功能是什么？如何协同工作？

三、（10分）8086如何响应一个可屏蔽中断请求？简述响应过程。

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

四、（15分）用其他指令完成和下列指令一样的功能: (1) REP MOVSB (2) REP LODSB (3) REP STOSB (4) REP SCASB

五、（15分）已知某8255A在系统中占用88~8BH号端口地址，现欲安排其PA，PB，PC口全部为输出，PA，PB口均工作于方式0模式，并将PC6置位，使PC3复位，试编写出相应的初始化程序。答案

一、1、F7.DCH 001001000111.10000110 BCD 2、4个地址 3、数据奇偶校验停止 4、0AAA40H 5、16

二、EU是执行部件，主要的功能是执行指令。BIU是总线接口部件，与片外存储器及I/O接口电路传输数据。EU经过BIU进行片外操作数的访问，BIU为EU提供将要执行的指令。EU与BIU可分别工作，当EU不需BIU提供服务时，BIU可进行填充指令队列的操作。

三、当8086收到INTR的高电平信号时，在当前指令执行完且IF=1的条件下，8086在两个总线周期中分别发出INTA#有效信号；在第二个INTA#期间，8086收到中断源发来的一字节中断类型码；8086完成保护更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

现场的操作，CS、IP内容进入堆栈，请除IF、TF；8086将类型码乘4后得到中断向量表的入口地址，从此地址开始读取4字节的中断处理程序的入口地址，8086从此地址开始执行程序，完成了INTR中断请求的响应过程。四、(1) LOOP1: MOV AL,BYTE PTR [SI] MOV ES:BYTE PTR [DI], AL INC SI 或: DEC SI INC DI 或: DEC DI LOOP LOOP1 (2) LOOP1:

MOV AL, BYTE PTR [SI] INC SI 或: DEC SI LOOP LOOP1 (3) LOOP1:

MOV ES:BYTE PTR [DI], AL INC DI 或: DEC DI LOOP LOOP1 (4) LOOP1:

CMP AL,ES:BYTE PTR [DI] JE EXIT

INC DI 或: DEC DI LOOP LOOP1 EXIT:

五、MOV AL， 80H OUT 8BH，AL MOV AL，ODH OUT 8BH，AL MOV AL，06H

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

OUT 8BH，AL

微机原理与接口技术（十）

一、填空题（每题5分，共5个题，总分25分）

1、10111B用十六进制数表示为 H，八进制数表示为 O。

2、微机的系统总线是连接CPU、存储器及I/O的总线，AB表示总线，DB表示总线，CB表示总线。

3、8086CPU是一个位的微处理器，具有位数据总线，位地址总线，可寻址空间为。 4、8086CPU可分为、两大部分。

5、用8k×1位的存储芯片，组成8k×16位的存储器，需用扩展，要用片。二、（10分）8086基本总线周期是如何组成的？各状态中完成什么基本操作？

三、（10分）设采用8251A进行串行异步传输，每帧信息对应1个起始位，7个数据位，1个奇/偶校验位，1个停止位，波特率为4800，则每分钟能传输的最大字符数为多少个？

四、（15分）某系统中8253占用地址为100H~103H。初始化程序如下： MOV DX， 103H MOV AL， 16H OUT DX， AL SUB DX， 3 OUT DX， AL

问：1、此段程序是给8253的哪一个计数器初始化？安排工作在哪种工作方式？

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

2、若该计数器的输入脉冲的频率为1MHZ，则其输出脉冲的频率是多少？

五、（15分）根据下列要求编写一个汇编语言程序:：代码段的段名为COD_SG 数据段的段名为DAT_SG 堆栈段的段名为STK_SG

变量HIGH_DAT所包含的数据为95 将变量HIGH_DAT装入寄存器AH，BH和DL 程序运行的入口地址为START 答案一、 1、11，21

2、地址，数据，系统 3、16，16，16，KB 4、RAM，ROM 5、分段，2

二、基本总线周期由4个时钟(CLK)周期组成，按时间顺序定义为T1、T2、T3、T4。在T1期间8086发出访问目的地的地址信号和地址锁存选通信号ALE；T2期间发出读写命令信号RD#、WR#及其它相关信号；T3期间完成数据的访问；T4结束该总线周期。

三、每帧占1+7+1+1=10位，波特率为4800 bit/s,故每分钟能传送的最大字符数为4800*60/10=28800个四、计数器0 工作于方式3 45.4KHZ 五、DAT_SG SEGEMNT HIGH_DAT DB 95 DAT_SG ENDS; STK_SG SEGMENT DW DUP(?) STK_SG ENDS;

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

COD_SG SEGMENT MAIN PROC FAR

ASSUME CS: COD_SG, DS: DAT_SG, SS: STK_SG START: MOV AX, DAT-SG MOV DS, AX MOV AH, HIGH_DAT MOV BH, AH MOV DL, AH MOV AH, 4CH INT 21H MAIN ENDP COD_SG ENDS END START

数据结构（八）

一、填空题（本大题共有5个题，每题5分，共25分，将正确答案填在空格处）

1.设栈的输入序列是1，2，„，n，若输出序列的第一个元素是n,则第i个输出元素是。 2.广义表（（a，b，c，d））的表尾是。

3.有一棵非空的二叉树（假设第0层为根结点）,其第i层上至多有个结点。

4.已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半法查找时90时，需进行次查找可确定成功。

5.已知二维数组A[10..20][5..10],每个数组元素占4个存储单元，若按行优先顺序存放数据元素，a[10][5]的存储地址是1000，则a[18][9]的存储地址是。二、（本题满分为10分）证明：树中的结点数等于所有结点的度数加1。

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

三、（本题满分为10分）如图所示有向图，采用dijkstra算法求出从顶点0到其它顶点的最短路径，并说明整个计算过程。

四、（本题满分为15分）已知，一棵二叉树中根遍历的结点序列为DCBGEAHFIJK，先根遍历的结点序列为ABCDEGFHJIK，画出对应的二叉树，并写出后根遍历的结点序列。

五、（本题满分为15分）试写出希尔排序的算法。

答案：

一、1.n-i+1 2.（） 3.2i 4.2 5.1208 二、根据树的定义，在一棵树中，除树根结点外，每个结点有且仅有一个前驱结点，也就是说，每个结点与指向他的一个分支一一对应，所以除树根之外的结点数等于所有结点的分支数（度数），从而可得树中的结点数等于所有节点的度数加1. 三、

（1）选<0,1>4 （2）选<1,2>1

（3）选<2,5>4 （4）选<0,3>6

（5）选<1,4>7 （6）选<5,6>8或选<4,6>6 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

四、

五、见课本

数据结构（九）

一、填空题（本大题共有5个题，每题5分，共25分，将正确答案填在空格处）

1.在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需向前移动个元素。 2.广义表（（a）,((b),c),(((d)))）的长度是。 3.深度为K的完全二叉树至少有个结点。

4.在一棵二叉树中，度为零的结点的个数为n0,度为2的结点的个数为n2，则有n0＝。 5.长度为255的表，采用分块查找法，每块的最佳长度是。

二、（本题满分为10分）有7个带权结点，其权值分别为：4，7，8，2，5，16，30，试以它们为叶子结点构造一棵哈夫曼树（要求按每个结点的左子树根结点的权值小于等于右子树根结点的权值的次序构造）

三、（本题满分为10分）在带头结点的单链表中查找数据域为x的结点，并返回首次找到的节点的序号。

四、（本题满分为15分）设有一组关键字（19，01，23，14，55，20，84，27，68，11，10，77），采用散列函数H(key)=key%13，采用开放定址法的二次探测再散列方法解决冲突，试在0到18的形式列地址空间中对该关键字序列构造散列表。

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

五、（本题满分为15分）二叉树采用链式存储结构，试设计一个算法计算一棵给定二叉树的所有结点数。答案：

一、1.n-i-1 2.3 3.2k-1 4. n2＋１ 5.15 二、构造的哈夫曼树为：

三、int locate(SNode *p,ElemType x) { int i=0;

SNode *q=p→next;

while(q!=null&&q→data!=x) { q=q→next; i++; }

if(q==null) return(-1);

else return(i); } 四、计算散列地址：

H(19)=19%13=6 H(01)=01%13=1 H(23)=23%13=10 H(14)=14%13=1(冲突) H1=(1+12)%19=2 H(55)=55%13=3 H(20)=20%13=7 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

H(84)=84%13=6(冲突) H1=(6+12)%19=7（冲突） H2=(6-12)%19=5

H(27)=27%13=1（冲突） H1=(1+12)%19=2（冲突） H2=(1-12)%19=0 H(68)=68%13=3（冲突） H1=(3+12)%19=4 H(11)=11%13=11

H(10)=10%13=10（冲突） H1=(10+12)%19=11（冲突） H2=(10-12)%19=9 H(77)=77%13=12 散列表为： 0 1 2 3 4 5 6 7 8 9 10- 11 12 13 14 15 16 17 18 10 23 11 77 27 01 14 55 68 84 19 20 ASL=（7*1+2*2+3*3）/12=20/12=5/3 五、int nodes(BTree *b) { int num1,num2; If(b==null) return(0)； else{

num1=nodes(b→left); num2=nodes(b→right); return(num1+num2+1); }} 数据结构（十）

一、填空题（本大题共有5个题，每题5分，共25分，将正确答案填在空格处）

1.设某二叉树前序为abdcef, 中序为dbaecf，则此二叉树的后序为。 2.具有4个顶点的无向完全图有条边。

3.已知二维数组A[10][20],每个数组元素占1个存储单元，若按列优先顺序存放数据元素，a[0][0]的存储地址是200，则a[6][12]的存储地址是。 4.具有n个结点的完全二叉树的深度为。

5. 已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半法查找时47时，需进行次查找可确定成功。二、（本题满分为10分）

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

（1）将图（a）中给定的树转换成二叉树（2）将图（b）中给定的二叉树转换成树（3）将图（c）中给定的森林转换成二叉树

三、（本题满分为10分）求以数据集（4，5，6，7，10，12，18）为结点权值所构造的哈夫曼树，并且计算出其带权路径长度。

四、（本题满分为15分）假设查找表以单链表的形式存储，试写出对此单链表进行顺序查找时的实现算法。

五、（本题满分为15分）写出一趟快速排序的算法。答案：一、 1. dbefca 2.6

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

3.332

4.∟ log2n」+1 5.4 二、

（1）（2）（3）

三、（4+5）*4+（10+6+7）*3+(18+12)*2=165 四、

struct Elemtype //数据元素的数据类型定义 {

keytype key; //关键字项 }；

struct Lnode {

Elemtype data ; struct Lnode * next ; } ;

int seqsearch (Lnode *L ,keytype s ) {

Lnode *p=L->next; int n=1;

while(p&&(p->data.key!=s)) {

p=p->next; n++; }

if(p) return n; else return –1; }

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

五、int Partition(SqList &L, int low,int high){ pivotkey=L.r[low].key; while(lowwhile(low= pivotkey) --high; L.r[low]←→L.r[high]；

while(lowreturn low; }

C语言程序设计（九）

一、填空题。写出下列程序的运行结果（本题共有5小题，每小题5分，满分25分） 1. main() {

int a,b; a=5; a=a+++4;

printf(“%d”,a); b=2; a=++-b;

printf(“%d\\n”,a);

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

}

程序运行结果是：（） 2. # include int f(int x) { static y=1; y++; x += y; return x; } main() { int k; k=f(3);

printf(\"%d %dn\}

程序运行结果是：（） 3.main() { int x; x=3; do {

printf(“%d”,x--); } while(!x); 程序运行结果是：（） 4.main()

{ int i,j,row,col,m,a[3][3]={{100,200,300},{28,72,-30},{-850,2,6}}; m=a[0][0]; for(i=0;i<3;i++) for(j=0;j<3;j++) if(a[i][j]更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

{ m=a[i][j]; row=i; col=j;} printf(“%d,%d,%d”,m,row,col); }

程序运行结果是：（） 5.以下fun函数的功能是将一个字符串的内容颠倒过来 #include “stdio.h” #include “string.h” void fun(char str[]) { int i,j,k;

for(i=0,j= ;i二、程序设计题（本题共有3个小题，第一题10分，剩余两题每题20分，满分50分） 1. 判断101-200之间有多少个素数，并输出所有素数。

2. 输入8个整数放入一维数组w中，输出交换前的数组；找出其中最小和最大数，并将他们分别与数组中的第一个元素和最后一个元素交换位置；输出交换后的数组。

3. 编写一个函数，输入n为偶数时，调用函数求1/2+1/4+...+1/n,当输入n为奇数时，调用函数 1/1+1/3+...+1/n

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

答案：一、 1. 91 2. 58 3. 3 4. -850,2,0

5. strlen(str)-1 j--或--j或j-=1 二、

1. #include \"math.h\" main() {

int m,i,k,h=0,leap=1; printf(\"\\n\"); for(m=101;m<=200;m++) { k=sqrt(m+1); for(i=2;i<=k;i++) if(m%i==0) {leap=0;break;}

if(leap) {printf(\"%-4d\ if(h%10==0) printf(\"\\n\");

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

} leap=1; }

printf(\"\\nThe total is %d\}

2. #include main()

{ int w[8],i,min,max,t;

printf(\"请输入8个整型数据:\");

for(i=0;i<8;i++) scanf(\"%d\ printf(\"交换前的数组:\");

for(i=0;i<8;i++) printf(\"%d\\ printf(\"\\n\"); min=0;

for(i=1;i<8;i++) {

if (w[i]for(i=0;i<8;i++) printf(\"%d\\ max=0;

for(i=1;i<8;i++) {

if (w[i]>w[max]) max=i; }

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

t=w[7];w[7]=w[max];w[max]=t; printf(\"交换最大值后的数组:\");

for(i=0;i<8;i++) printf(\"%d\\ printf(\"\\n\"); }

3.#include \"stdio.h\" main() {

float sum; int n; while (1) {

scanf(\"%d\ if(n>1) break; }

if(n%2==0) {

printf(\"Even=\"); sum=dcall(peven,n); } else {

printf(\"Odd=\"); sum=dcall(podd,n); }

printf(\"%f\}

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

float peven(int n) { float s; int i; s=1;

for(i=2;i<=n;i+=2) s+=1/(float)i; return(s); }

float podd(n) int n; { float s; int i; s=0;

for(i=1;i<=n;i+=2) s+=1/(float)i; return(s); }

float dcall(fp,n) float (*fp)(); int n; { float s; s=(*fp)(n); return(s); }

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

C语言程序设计（十）

一、填空题。写出下列程序的运行结果（本题共有5小题，每小题5分，满分25分） 1. main() { int k; float s;

for (k=0, s=0; k < 7; k ++) s += k/2; printf(\"%d, %fn\}

程序运行结果是：（） 2. 函数 void f(char s[ ], char t[ ]) { int k=0; while (s[k]=t[k]) k++; } 等价于

void f(char *s, char *t) { while ( ); }

3. # include # include

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

main()

{ int a=1,b=4,c=2;

float x=10..5 , y=4.0 , z; z=(a+b)/c+sqrt((double)y)*1.2/c+x; pritnf(\"%f\\n\

程序运行结果是：（） 4.int fun(int *x,int n) { if (n==0) return x[0]; else return x[0]+fun(x+1,n-1); } main()

{ int a[]={1,2,3,4,5,6,7}; printf(“%d”, fun(a,3)); }

程序运行结果是：（） 5. 以下程序的功能是利用指针指向三个整型变量，并通过指针运算找出三个数中的最大值 # include main()

{ int x,y,z,max, *px, *py, *pz, *pmax; scanf(“%d%d%d”,&x,&y,&z); px=&x; py=&y; pz=&z; pmax=&max; ; if(*pmax<*py) *pmax=*py; if(*pmax<*pz) *pmax=*pz; printf(“max=%d”,max); }

二、程序设计题（本题共有3个小题，第一题10分，剩余两题每题20分，满分50分） 1. 写一个函数，求一个字符串的长度，在main函数中输入字符串，并输出其长度。更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

3. 编写程序完成矩阵转置,即将矩阵的行和列对换：如将矩阵 1 2 3 4 倒置为 1 5 9

5 6 7 8 2 6 10 9 10 11 12 3 7 11 4 8 12 答案：

一、1. 6,90 2. *s++=*t++ 3. 13.700000 4. 40 5. *pmax=*px 或 *pmax=x或 max=x或 max=*px 更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

二、 1. main() { int len; char *str[20];

printf(\"please input a string:\\n\"); scanf(\"%s\len=length(str);

printf(\"the string has %d characters.\}

length(p) char *p; { int n; n=0;

while(*p!='\\0') { n++; p++; }

return n; }

3. #include “stdio.h” #define ROW 3 #define COL 4 main()

{ int i,j,a[ROW][COL], a[ROW][COL]; for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) scanf(“%d”,&a[i][j]);

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) b[j][i]=a[i][j]; for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) printf(“%5d”,b[i][j]); } }

; if(*pmax<*py) *pmax=*py; if(*pmax<*pz) *pmax=*pz; printf(“max=%d”,max); }

二、程序设计题（本题共有3个小题，第一题10分，剩余两题每题20分，满分50分） 1. 写一个函数，求一个字符串的长度，在main函数中输入字符串，并输出其长度。

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

3. 编写程序完成矩阵转置,即将矩阵的行和列对换：如将矩阵 1 2 3 4 倒置为 1 5 9

5 6 7 8 2 6 10 9 10 11 12 3 7 11

4 8 12 答案：

一、1. 6,90 2. *s++=*t++ 3. 13.700000 4. 40 5. *pmax=*px 或 *pmax=x或 max=x或 max=*px 二、 1. main() { int len; char *str[20];

printf(\"please input a string:\\n\"); scanf(\"%s\len=length(str);

printf(\"the string has %d characters.\更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

}

length(p) char *p; { int n; n=0;

while(*p!='\\0') { n++; p++; }

return n; }

3. #include “stdio.h” #define ROW 3 #define COL 4 main()

{ int i,j,a[ROW][COL], a[ROW][COL]; for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) scanf(“%d”,&a[i][j]); for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) b[j][i]=a[i][j]; for(i=0;i<=ROW;i++) for(j=0;j<=COL;j++) printf(“%5d”,b[i][j]); } }

更多专升本资料请到山东校园网：www.xyw.me

山东校园网：www.xyw.me 山东招生考试资讯网

更多专升本资料请到山东校园网：www.xyw.me 38

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文