TFT/LCD驱动IC NT35510芯片手册datasheet
TFT/LCD驱动IC、手机显示屏驱动IC-NT35510，文档详细讲解了该芯片的接口定义，以及驱动显示屏的解决方案.NOVATEKPRELIMINARYNT355105.4.2 MDD/ Link Packet Descriptions by the NT355101625.4.3 Writing Video Data to Memory Sequence.......1725.44 Writing Register Sequence...….…,…1725.4.5 Reading video Data from Memory Sequence.7735.4.6 Reading Register Sequence………,…,…,…,…,…,…,…,…,…,…,…,…,…,…,…,…,………735.4.7 Hibernation Setting-..,.,…,…T745.4.8 MDD/ Deep Standby Mode Setting-……,……,…,…,…,…,…,…,………,…,…1755.5 INTERFACE PAUSE1775. 6 DATA TRANSFER BREAK AND RECOVERY.1785.7 DISPLAY MODULE DATA TRANSFER MODES,58RGB| NTERFACE,,nn,,…,…,,,……18158.1 Genera/ Description.…,.,.,…,…1815.8.2 RGB Interface Timing Chart1825.8.3 RGB Interface Mode Set.1835.8.4 RGB Interface Bus Width Set.18759 FRAME MEMORY,……,,,191591 Configuration…....…n1915.92 Address Counter….……………,7925.9.3 Interface to Memory Write Direction.........1935.9.4 Frame Memory to Display Address Mapping.......n…1945.10 TEARING EFFECT INFORMATION1955.10.1 Tearing Effect Output Line1955.10.2 Tearing Effect Bus Trigger..........面面面面面面面aa面面看日自DB自2005.11 CHECKSUM2125.12 POWER ON/OFF SEQUENCE2145. 12. 1 Case 1-REsX line is held High or Unstable by Host at Power On..................2155. 12.2 Case 2- ResX line is held Low by host at power on...e.2165.12.3 Uncontrolled power off2765.13 PoWER LEVEL MODES wmmmmmm2175.13.1 Definition2175.13.2 Power level Mode flow chartn2185.14 RESET FUNCTION…112205.14. 1 Register Default value2205.14.2 Output or Bi- directiona/{o)Pins………,,,…,……………,…,…,,…,…………,……,………2225.14.3 Input Pins………,…,,…,…2221028/20113Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT355105.15 SLEEP OUT-COMMAND AND SELF-DIAGNOSTIC FUNCTIONS OF THE DISPLAY MODULE2235. 15. 1 Register loading Detection.....2235.15.2 Functionality Detection2245.15.3 Chip Attachment Detection…….2255.16 DISPLAY PANEL COLOR CHARACTERISTICS mmmm 2265.17 GAMMA FUNCTI0N..…,………面国面面面国面2275.18 BASIC DISPLAY MODE■日量2285.19 NSTRUCTION SETTING SEQUENCE2295.19.1 Sleep In/Out Sequence…,…,…,…,…,…,…,…,…,…,,…,…,…,…,,…2295192 Deep Standby Mode Enter/ Exit Sequence……2305.20 INSTRUCTION SETUP FLOW2315. 20.1 Initializing with the Built-in Power Supply circuits2315. 20.2 Power OFF Sequence232521 MTP WRITE SEQUENCE…….2335.22 DYNAMIC BACKLIGHT CONTROL FUNCTION234522.1 PWM Control Architecture面面面面面面a面a面面2365. 22.2 Dimming Function for LABC and Manual Brightness Control6.22. 3 Dimming Function for CABC and Force PWM Function,2445.22.4 PWM Signal Setting for CABC and LABC2455.2.5 Content Adaptive Brightness Contro/CABC)………,2475.22.6 Ambient Light Sensor and Automatic Brightness Contro(LABC)…,…,…,…,…,…,…,…,…,………2485.23 COLUMN, 1-DOT, 2-DOT, 3-DOT AND 4-DOT INVERSION (VCOM DC DRIVE2556 COMMAND DESCRIPTIONS2566.1 USER COMMAND SET256NOP0000)....,.…260SWRESET: Software Reset (0100h ...267RDDID: Read Display ID(0400h-0402h)262RDNUMED: Read Number of Errors onRDDPM: Read Display Power Mode(0A00h)............264RDDMADCT: Read Display MAdo间0B0oh),…,265RDDCOLMOD: Read Display Pixel Format0cooh)………266RDDM: Read Display image Mode间 0D00h)……,…………………………………………………………267RDDSM: Read Display signa/Mode(0E00h)……................,…………………268RDDSDR: Read Display Self-Diagnostic Result(sLPN: Sleep In(1000h)-……2701028/20114Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT35510SLPOUT: Sleep Out(100h)……,…,…,…,…,…,…,…,…,……272PTLON: Partial Display Mode On(1200h).........274NORON: Norma| Display Mode On(1300h)...............………275INVOFF: Display Inversion Off (2000h)276yvoN: Display Inversion On(2100b)….......……量道量道面道量温量量量面量面面面面目面面277ALLPOFF: All Pixel Off(2200h)278ALLPON: All Pixel On(2300h280GAMSET: Gamma Set(2600h)…,,,,,,…,282DISPOFF: Display ofi(2800b)….……....,,…,…,…,…,……,283DISPON: Display On( 2900b)284CASET: Column address set(2A00h~2A03h).……,,…285RASET: Row Address Setn287RAMWR: Memory Write(2c00h)289RAMRD: Memory290PILAR: Partial Area(3000h-3003)....∴291TEOFF: Tearing Effect Line OFF (3400h)面面面面面a面面294TEON: Tearing Effect Line ON (3500h)295MADCTL: Memory data Access Control (3600h)..............................296DMOFF: dle mode o(3800……299IDMON: ldle Mode On (3900h).......300COLMOD: Interface Pixel Format 3A00h)302RAMWRC: Memory Write Continue(3c00h)…..........……303RAMRDC: Memory Read Continue(3E00h)……,…,,…,,,…,…304STESL: Set Tearing Effect Scan Line(4400h-4401)...........305GSL: Get Scan Line(4500h-4501h),.…,…,…,…,…,…,…,…,…,…,…,,…307DPCKRGB: Display Clock in RGB Interface(4A00h)308DSTBON: Deep Standby Mode On(4F00h)BIEaIESEBBSEBSEEEE309WRPFD: Write Profile value for Display (5000h-500Fh)........................310WRDISBV: Write Display Brightness(5100h)...………311RDDISBV: Read Display Brightness(5200h)…,…312WRCTRLD: Write CTRL Display(5300h)………313RDCTRLD: Read CTRL Display value(5400h)……,.....,…....……,…,…………315WRCABO: Write Content Adaptive Brightness Contro(5500h)…………………317RDCABO: Read Content Adaptive Brightness Control(5600h)…….…,…,…,…,…,……,…,…,……………………318NRHYSTE: Write3191028/20115Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT35510WRGAMMSET: Write Gamma Setting(5800h-5807h)..eec.321RDFSVM: Read Fs Value MSBs(5A00h)...........323RDFSVE: Read Fs value lsBs(5B0h)..............….……324RDMFFSVM Read Median Filter Fs value MSBs (cooh).325RDMFFSVL: Read Median Filter Fs value LSBs(5D00h)326WRCABCMB: Write CABC minimum brightness(5E00h).,…,…,…,………,,………327RDCABCMB: Read CABC minimum brightness(5Fooh).........328WRLSCO: Write Light Sensor Compensation Coefficient value(6500h~6501h)………,……………,…,…,…………329RDLSCCM: Read Light Sensor Compensation Coefficient Value MSBs(6600h )......,.........-. 330RDLSCCL: Read Light Sensor Compensation Coefficient Value LSBsRDBWLB: Read Black/White low Bits(7000h)332RDBkX: Read Bkx (7100h)333RDBky: Read Bky(7200h)334RDWX: Read Wx( 7300b)............. e..335RDWy: Read wy(7400h)…336RDRGLB: Read Red/Green Low Bits(7500h).......337RDRx: Read Rx(7600).……338RDRy: Read Ry(7700b)..........339RDGX: Read…,,,,,,,,340RDGy: Read Gy(7900h)....................n…341RDBALE: Read blue/ color low Bits(7A00h)……n,,342RDBx: Read Bx(7B00b)-..……,,,343RDBy: Read By(7c00b),,,,.,.,.,.,.,.,.,...,.,.,.,.,.,.,.,…,…344RDAx: Read ax(7D0oh)………,…345RDAy: Read Ay(7E00h)……,…,…,…346RDDDBS: Read DDB Start(A100h-A104h347RDDDBC: Read DDB Continue(A800h-A804h)349RDFCS: Read first checksum(AA0oh)……351RDCCS: Read Continue Checksum(AF00h)-.…………352RDID1: Read iD1 value(DAooh).ee..353RDD2: Read D2 Value(DB0oh)……354RDD3: Read D3vaue( COoh)……………,……………,…………………,…3557 SPECIFICATIONS…3567.1 ABSOLUTE MAXIMUM RATINGS.3567.2 ESD PROTECTION LEVEL3561028/20116Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT355107. 3 LATCH-UP PROTECTION LEVEL3567.4 LIGHT SENSITIVITY3567. 5 DC CHARACTERISTICS3577.5.1 Basic characteristics.357752MP/ Characteristics35975.3 MDD/ Characteristics wwwwwww 3617.5. 4 Current Consumption in Standby Mode and DSTB Mode..3627.6 AC CHARACTERISTICS3637.6.1 Parallel Interface Characteristics (80-Series McU)36376.2 SerialInterface Characteristicsaaaassaaaaussuaaaaaaaaaaaaaaaaaaaa3647.6.3 12C Bus Timing Characteristics36576.4 RGB Interface Characteristics3667.6.5 MIP/DS/ Timing Characteristics3677.6.6 MDD/ Timing Characteristics........3717.6.7 Reset Input Timing3728 REFERENCE APPLICATIONS. G.…3738.1 MICROPROCESSOR INTERFACE3738. 2 CONNECTIONS WITH PANEL. m..n..37810/28/2011Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT35510REVISION HISTORYPrepareChecked ApprovedVersionContentsDatebyy0.00OriginalKevinn swDennis2010/02/12Page 9, remove 32ORGB X 480Page 10, Features, remove 32ORGB X 480 and mux descriptionVGHO VGLO for gate control signals, remove VDDIM/SSIMPage11, update power voltage rangePage 12, Block diagramPage 13 to 22Add: VDD DET, DIOPWR, PSWAP, DSWAP, VGHO, VGLO, VRGHVREFCP, CSP, CSN, LVGL, C61P, C61N, VRGH, VREF, GOUT.Remove: VDDIMSSIM. VDDELUpdate: MVDDL,VGL,VGH, Test pinsPage23, update IF tablePage 51 to 66: update SPl, M3=1 setting in figurePage 102, 103, change DSIM, DSiG bit Reg to OXB 100Page 115, 124 Add WrPFD 50h on tablePage201, modified to 480X864 memoryPage202, Remove 320x480Page204, update whole Frame memory tablePage 205, TE map to 480 lines, DOPCTR change to B100hPage207, tvdI TBDPage225, 226, update VDD in figurePage227, Modes to 7Page232, Sout update to Gout0.01Page235, Add chip attachment Detection sectionKevinSWDens2010/03/17Page237, update Gamma StructurePage255, 270, update FOSC, ExamplePage266, update KB CLEDPage272, Add inversion sectionPage273, 274, Power ArchitecturePage275, update DIOPWRVREFCP, VGMP1,VGLOPage276, update C61P/N, LVGL, VGLO, VRGH,VREFCP, DIOPWR,VGMP 1/2VGMNVGSPVGSNPage291, change name to RAMKPPage306 to 312, remove 320x 480 resolution settingPage337, 5400h Cmd add a andg bitPage385, Absolute Max Rating for MV Hv, remove VDDIMPage 386, VDDIM removePage387, Vdev value modifiedPage402, 403, Remove MVDDI in notePage406, Remove 320 X 480, update 360X640 Sout sequencePage 173 to 181, MDDI windowless packetPage377, 379, A1, A8 cmd updatePage387 to 396, VDDI to 3.3VPage362 to 37670h to 7Eh cmd default valuePage28, 29, 30, 40, 41, 42 MPU figure updatePage 12, 274 Block and power architecture update10/28/20118Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT35510Page 10, remove 36ORGB X 640, Add 480RGBx720Page 11, update GPo[3: 01pdate VGHO, VGLOge 13, update Block DiagramPage 18, update IM, GPO, VSEL, and EXB1TPage 20, update VGLO, LVGLPage 21, update VGLX,VGL REG, Remove CP6 P/NPage 23, update VDD BCPage 24, update ContACT1-4, VSSIDUMPage 25, update iF description tablePage 207, update Address CounterKevinDennis2010/0406Page 235, update Resolution DataPage 252, remove CLED VOLPage 271, remove KB CLED_ VOLPage 277, add 4 dot inversionPage 306, 308, 313, 326 resolution update, remove nHD, add 480X720Page 384, update absolute voltagePage 385, update DC specPage 386, update Note3, Note5Page 405. update resolutionPage 406. update Alignment Mark-Page10,11205,206,234,305307,312,325404, update resolutionPage 13, update Block diagramPage 17-24, update pin description(MDDI not support DSWAPUpdate TEIR, TE_L, DSTB SEL, RESX, VSEL VREF PWR 12C_SDAremove VDD BD, ENDIOVPagB104121ric data type 0x24Page 134, update eotP optionPage 175, update MDDI support typPage 176, 177, update sub frame header, link shut down packetSWDennis2010/05/18Page 179, 180, update skew calibration packet, client capability packetPage 184, update packet type is 20Page 209, 214, update tE off, output is low, tering effect bus triggerPage 241, update gamma to 10 bits settingPage 276, update 3-dots inversionPage 384 update VIH, VIL, VoH,VOLPage 388, update hibernation wake upPage 390, 392 update Note2-Remove pad chapter to application note10/28/20119Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformationNOVATEKPRELIMINARYNT35510Page 14, update block diagram of RGBBPPage 16, update WRX/SCL/2C SCL, sDI/2C SDAPage 19-25, update IM3 pin description, RGBBP(remove 12C SA1)OSC Test description, KBBC to test pinPage 21, update VREF PWr descriptionPage 26, update IM tablePage 42-44, update MPU read scriptionPage 49-52, update SPl+RGB or SPl+MDDI description0.04Page 60, update 12C AddressKevinSWDen201007/27Page 181, 182, update 16 bit SPI pause descriptionPage 187-189, update RGB figurePage 200, update TE waveform in RGB mode 2Page 237, MTP sequencePage 238-258, update one dimming control for LABC CABcremove KBBc function descriptionPage 260, update 0X04 Cmd, remove KBBC CmdPage 262, update 0XA 1,0xA8 CmdRemove all the KBBc related function registerPage11,12,190,191,219,284-287,291,304,376,remove 480RGBX 360Page 15, update MTP PWR application voltagePage 16, update CSX, RDX, DC/X, SDI, SDOPage 18, update DSWAPPage 19, correct typo for IM[3: 0]in MDDI+SCL(falling edge)Page 38&44, update typo for data format in table0.05Page 53, update read data 8-8-8-bit only in SPIKevinDenn2010/10/18Page 183, 184, update note for min porch of RGB interfacePage 232, update MTP sequence and MTP PWR voltagePage 235, 236, remove PWM ENH OE bit(keep x2Page 312, 314, update typo for BCTRL and BLPage 371, 372: update figuresPage 373: update figure, add RGB+l2CPage 374: update figures, IM settingPage 375: update figures, IM settingPage 15, update DVDD typicage 129, update typo in figure of AwERPage 194, update typo for Hsync218 add condition of irregulaoffPage 219, 255, update command name typo of 05h commandPage 228-231, update typo in figuresPage 234, update typo for ALS in figure 5. 22.10.1Page 235, update CLED VOL bit in figure 5. 22.2KevinDennis2010/12/24Page 312, 314, update typo for BCTRL bl bitsPage 316, update typo in flow chartPage 346, update description of parameterPage 355, update maximum rating for VGH, GlxPage 358, 359, update 2 lane description in conditionPage 362, update pin name typo in figure-Page 376, update typo for CRGB condition10/28/201110Version o 8With respect to the information represented in this document, Novatek makes no warranty, expressed or implied, including the warranties of merchantabilityfitness for a particular purpose, non-infringement, or assumes any legal liability or responsibility for the accuracy, completeness, or usefulness of any suchinformation
- 2020-12-05下载
- 积分：1
上海大学数据结构试卷及答案
很好的考试复习资料，内容很多，讲解很细致，而且涉及的也是重点数据结构试卷(一)参考答案选择题2.C3.DC 5. A6,C7.C8,B9.810.B填空题1.(F+!2.0(n),0(n1,4. s->rext=p-7nexl: y>neext=sn, 2e6.m=2了,CBA8.4,1610.n-1、应用题1.链式存储结构略,前序 ABDEL,中序 DBEAC,后序 DEBCA,2.哈夫曼树略,WPL=783.(i8,5,16,19,21,23),(5,16,21,19,18,23)h1012345674.线性探测:链地址法:h2->1人8∧1025322768h4->25->326865.深度:125364,广度:123456,最小生成树T的边集为E={(1,4),(1,3)(3,5,(,如,(.6)}四、算法设计题1.设计判断单链表中结点是否关于中心对称算法typedef struct (int s[100]; int top, y sqstack;int lklistsymmetry(iklist *head)sqstack stack; stack top=-1; Iklist"p;forip=head;pl=O; p=p->next)(stack. op++;stack s[stack top=p->data; 3for(p=head;pl=0;p=p->next)iE (p->data==stack s(stackLop!)stack top=stack top- 1; else return(0);return(1);2.没计链式存储结构上建立一楳二又树的算法。typedef char datatype,typedef struct node (datatype data; struct node *lchild, *rchild; bitreevoid createbitree( bilree*&bt)char ch; scanf("%c, &eif(ch==")(bt=0; return; Jbt=(bitree*)malloc(sizeof(bitree)); bt->data=chreatebitree(bt->lchild); createbitree(bt->rchild);3.设计判断一棵二叉树是否是二义排序树的算法。int minnum=-32768, flag=1typedef struct nodefint key; struct node"Child, *rchild; bitree;yoid inorder ( bitree *bt)if (bt =0)[inorder(bt->child ); if(minnum>bt->key)flag=0; minnum=bt->key, inorder (bt->rchild); h数据结构试卷(二选择题(24分)1.卜面关于线性表的叙述错误的是(D)(A)线性表采用顺序存储必须:用一片连续的存储空间(B)线性表采用链式存儐不必山用一片迕续的存储空闫(C)线性表用链式存便丁插入和删除操作的实现D)线性表釆用顺序存储便亍插入和删除操作的实现设哈大曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有(A界个空指针域,9有叶万为的纸且2(A)2m-1(B)2mC)2m+1妤没顺序循环队列Q0:M1]的头指针和尾指针分别为P和R,头指针F总是指向队头元素的前一位置尾指针R总是指向队尾元的当前位置,则该循环队列中的元素个数为()(A)R-T(B)F-R(C)(R-F+M)%M()(F-R+M)%M√4!设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为A(A)BADC(B)BCDA(C CDAB(D) CBDA5.设某完全无向图有n个顶点,则该完全无向图中有(A条边(A)n(n-1)/2(B)n(n-1)(C)n26.设某棵二叉树中有2000个结点,则该二叉树的最小高度为(O)。(C)11D)12设采图中有m个顶点,则该有向图对应的剑趣中有()个表头结点(B)n(D)2n-18.设一组初始记录关键字序列(5,2,6,3,8),以笫一个记录关键字5为基准进行一趟快速排序的结果为(C)。(A)2,3,5;8,6(B)3,2,5,8,6(C)3,2,5:6,8①D)2,3,6,5,8、填空题(24分)1.为了能有效地应用HASH查找技术,必须解决的两个问题是和下面程序段的功能实现数据x进栈,要求在下划线处填上正确的语句typedef struct (int s[ 100]; int top: f sqsiack;void push (sqstack &stack, int x)if( stackop==m-1) printf(“ overflow”)lies9tk二x;“a少+:3.中序遍历二叉排序树所得到的序列是有度序列(填有序或无序铁邀神厅的最间复弟度为1),平均时间复杀度为地D(3设某倮二叉树中度数为0的结点数为N,度数为1的结点数为N,则该二叉树中度数为2的结点数若采用二叉链表作为该二叉树的存储结构,则该二叉树中共有山+41个空指针域6.设某无向各中顶点数和边数分别为n和e,所有顶点的度数之和为d,则e=7.设一缃初始记录关键字序列为(55,63,44,38,75,80,31,56),则利用筛选法建立的初始堆为8.改某无向图G的邻接表为2->1>3又v--1->4->2·从点W开始的深度优先遍历序圳为1,24:切度优先遍历序列为省三、应用题(36分)].设一组初始记录关键字序为(45,80,48,40,22,78),则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果2.设指针变p指向双向链表中结点A,指针变量q指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结京的两个指针域分别为11ink和 rlink)a设一组有序的记录关键字序圳为(13,18,24,35,47,50,62,83,90),查找方法用二分查找要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度4设一棵树T中边的集合为联A,B),(A,C,(A,D),(B,E),(C,F,(C,G)},要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树5.设有无向图G(如右图所示),要求给出用普里姆算法构造最小生成树所走6过的边的集合。6.设有—组初始记录关键字为(45,80,48,4,2,178,要求构造一楔二(56叉排序树并给出构造过程。四、算法设计题(16分)1.设有一组初始记录关键字序列(K,K2,…,K),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K,右半部分的每个关键字均大于等于K2.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C用链式存储结构表示数据结构试卷(二)参考答案选择题ltd 2. B5,A7,B8.C二、填空题构造一个好的HASH凼数,确定解决冲突的方法2. stack top+t, stack s[stack top ]=3.有序4.0(n2),0( logan)5.N-1,2N+N6.d/27.(31,38,54,56,75,80,55,638.(1,3,4,2),(14)应用题1.(22,40,45,48,80,78),(40,45,48,80,22,78)2. q>llink=p: g->rlink=p->rlink; p->rlink->link=q; p->rlink=q·3.2,ASL=91*1+2*2+3*4+4*2)=25/94.树的链式存储绪构略,二叉树略E={(1,3),(1,2),(3,5),(5,6),(6,4)}6.略四、算法设计题1.设有组初始记录关键字序列(K1,K2,…,Kn),要求设计一个算法能够在0(n)的时间复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于K1,右半部分的每个关键字均大于等于KYoid quickpass(int r[, int s, int t)int i=s,j=t, x=r[s]While(inext: p->data=g->data: p->next=g->next: free(q)B)gp->next: g->data=p->data: p->next=g >next free(g):(C)q=p->next: p->next=q->next: free(q)(D)q=p->next: p->data=q->data: free q)4.设有n个待排序的记录关键字,则在堆排序中需要(小个辅助记录单元(A)1(B)n(c)nlogen5.设一组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的一趟快速排序结束后的结果为(A)10,15,14,18,20,36,40,21(B)10,15,14,18,20,40,36,2I(C)10,15,14,20,18,40,36,21(D)15,10,14,18,20,36,40,21y/设二叉排序树中有n个结点,则在二叉排序树的平均平均查找长度为)(A)0(1)(B)0(10g2n)((D)O(n2)7.设无向图G中有n个顶点e条边,则其对应的邻接表中的表头结点和表结点的个数分别为(D(B)e,nC)2D)n,28.设某强连通图中有n个顶点,则该强连通图中至少有(C)条边(A)n(n-1)(B)n+1D)n(+19.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列)方法可以达到此目的(A)快速排序(B)堆排序(C)归并排序D)插入排序0下列四种排序中()的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序二、填空殖(48分,其中最后两小题各6分)数据的物理结构主要包括座不构利和环结堆两种情况设一棵完全:叉树中有500个结点,则该二叉树的深度为4:若用二叉链表作为该完全二叉树的存情结构,则共有55个空指针域3.设输入序列为1、2、3,则经过栈的作用后可以得到种不同的输出序列。4.设有向图G用邻接矩阵An]「m作为存储结构,则该邻接矩阵中第i行上所有元素之和等于顶点i的友,第1列上所有元素之和等于顶点i的入区毕设哈夫曼树中共有n小结点,则该哈夫曼树中有日个度数为1的结点6.没有向图G中有n个顶点e条有向边,所有的顶人度散之和为d则形和d的关系为=e遍历二义排序树中的结点可以得到一个递增的关键字序列(填先序、中序或后序)8.改奁找表中有100个元素,如果川二分法查找方法查找数据元素X,则最多需要比较次就可以断定数据元素K是否在查找表中9.·不论是顺序存储结构的栈还烂链式存储结构的栈:其入饯和出栈榤作的间复柒度均为的10.设有a个结点的完全一义树,如果按照从自上到下、从左到右从1开始顺序编号,则第i个结点的义结点编号为“,右孩子结点的编号为2计11.设一组初始记录关键字为(72,73,71,23,94,16,5),则以记录关键字72为基准的·趟快速排序结果为!2.设有向图G中有向边的集合F=(,,,,key==k)Y七; else if(t->key>k)tt>lchd;lse七飞→YC三、算法设计题(22分设计在单链表中删除值相同的多余结点的算法2.设计-个求结点x在二叉树中的双亲结点算法。数据结构试卷(三)参考答案、选择题B4.A5.A6.B7.D8.C9.B10. D第3小题分析:首先用指针变量q指向结点A的后继结点B,然后将结点B的值复制到结点A中,最后删除结点B第9小题分析;9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数,而堆排序只需要在初始堆的基础上再进行10次筛选即可,每次筛选的时间复杂度为0(1ogn)。土、填空题1.顺序存储结构、链式存储结构2.9,5013.54.出度,入度6.7.中序8.79.0(1)10.豆/2,2i+111.(5,16,71,23,72,94,73)12.(1,4,3,2)13. j+l, hashtable[i]. key==k14. return(t),t=t-rchild第8小題分析:二分査找的过程可以用一棵二叉树来描述,该二叉树称为二叉判定树。在有序表上进行分查找时的查找长度不超过二叉判定树的高度1+log2n三、算法设计题设计在单链表中删除值相同的多余结点的算法。typedef int datatype;typedef struct node datatype data; struct node *next; lklistvoid delredundant (lklist *&head)Iklist *p,响q,*s;for(p=head; pl=0; p=p->next)tor(q=p>nex s=4;q!=0;if (q->data==p->data)[s->next=q->next; free(q); q=s->next; 1else (s=q, q=q->next; y。2.设计个求结点x在二义树中的双亲结点算法。typedef struct node (datatype data; struct node *Child, *rchild; bitree;bitree*q[20]; int r=0, f=0, flag=0void preorder (bitree * bt, char x)
- 2021-05-07下载
- 积分：1
